1700539447
1700539448
（11.6）
1700539449
1700539450
1700539451
如果推荐的次数足够多，k足够大，那么会趋近于真实的菜做得好吃的概率p。
1700539452
1700539453
1700539454
1700539455
利用阶段：已知所有的菜做得好吃的概率，决定该如何推荐？如果每道菜都被推荐了很多遍，就可以计算出每道菜做得好吃的概率，于是只需推荐最大的那道菜。
1700539456
1700539457
探索和利用的平衡是一个经久不衰的问题。一是，探索的代价是要不停地拿用户去试菜，影响客户的体验，但有助于更加准确的估计每道菜好吃的概率；二是，利用会基于目前的估计拿出“最好的”菜来服务客户，但目前的估计可能是不准的（因为试吃的人还不够多）。
1700539458
1700539459
1700539460
1700539461
1700539462
1700539463
1700539464
1700539465
如何平衡探索和利用呢？可以使用-greedy算法，即每当客人到来时，先以的概率选择探索，从N道菜中随机选择（概率为/N）一个让客人试吃，根据客人的反馈更新菜做得好吃的概率；然后，以1− 的概率选择利用，从N道菜中选择好吃的概率最高的菜推荐给用户。
1700539466
1700539467
1700539468
1700539469
1700539470
-greedy算法也存在一些缺点，比如，在试吃次数相同的情况下，好吃和难吃的菜得到试吃的概率是一样的：有一道菜持续得到好吃的反馈，而另一道菜持续得到难吃的反馈，但在-greedy中，探索两道菜的概率是一样的，均为/N；在估计的成功概率相同的情况下，试吃次数多的和试吃次数少的菜得到再试吃的概率是一样的：假设有两道菜，第一道菜50人当中30个人说好，第二道菜5个人当中3个人说好，虽然两道菜的成功概率都是60%（30/50 = 3/5），但显然反馈的人越多，概率估计的越准。再探索时，应该把重心放在试吃次数少的菜上。
1700539471
1700539472
1700539473
总结一下，-greedy生硬地将选择过程分成探索阶段和利用阶段，在探索时对所有物品以同样的概率进行探索，并不会利用任何历史信息，包括某道菜被探索的次数和某道菜获得好吃反馈的比例。
1700539474
1700539475
不妨让我们忘记探索阶段和利用阶段，仔细想想如何充分地利用历史信息，找到最值得被推荐的菜。
1700539476
1700539477
1700539478
1700539479
1700539480
观测 1：如果一道菜已经被推荐了k遍，同时获取了k次反馈，就可以算出菜做得好吃的概率： ．
1700539481
1700539482
（11.7）
1700539483
1700539484
1700539485
当k趋近正无穷时，会趋近于真实的菜做得好吃的概率 p。
1700539486
1700539487
1700539488
1700539489
1700539490
1700539491
1700539492
观测 2：现实当中一道菜被试吃的次数k不可能无穷大，因此估计出的好吃的概率和真实的好吃的概率 p 总会存在一个差值Δ，即Δ。 基于上面两个观测，我们可以定义一个新的策略：每次推荐时，总是乐观地认为每道菜能够获得的回报是+Δ，这便是著名的置信区间上界（Upper Confidence Bound，UCB）算法。最后只需解决一个问题：计算真实的概率和估计的概率之间的差值Δ。
1700539493
1700539494
在进入公式之前，让我们直观的理解影响Δ的因素。对于被选中的菜，多获得一次反馈会使Δ变小，最终会小于其他没有被选中的菜；对于没被选中的菜，Δ会随着轮数的增大而增大，最终会大于其他被选中的菜。
1700539495
1700539496
