打字猴:1.700539458e+09

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