1700539430
1700539431
（2）给客人推荐一道菜，客人接受则留下吃饭（Reward=1），拒绝则离开（Reward=0）。
1700539432
1700539433
（3）记录选择接受的客人总数 total_reward。
1700539434
1700539435
为了由浅入深地解决这个问题，我们先做以下三个假设。
1700539436
1700539437
（1）同一道菜，有时候会做得好吃一些（概率＝p），有时候会难吃一些（概率 = 1−p），但是并不知道概率p是多少，只能通过多次观测进行统计。
1700539438
1700539439
（2）不考虑个人口味的差异，即当菜做得好吃时，客人一定会留下（Reward=1）；当菜不好吃时，客人一定会离开（Reward=0）。
1700539440
1700539441
（3）菜好吃或不好吃只有客人说的算，饭馆是事先不知道的。
1700539442
1700539443
探索阶段：通过多次观测推断出一道菜做得好吃的概率。如果一道菜已经推荐了k遍（获取了k次反馈），就可以算出菜做得好吃的概率
1700539444
1700539445
1700539446
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
