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
1700539497
下面正式地介绍如何计算Δ，首先介绍Chernoff-Hoeffding Bound：假设Reward1,…,Rewardn 是在[0,1]之间取值的独立同分布随机变量，用表示样本均值，用 p 表示分布的均值，那么有
1700539498
1700539499
1700539500
．
1700539501
1700539502
（11.8）
1700539503
1700539504
1700539505
当Δ 取值为时，其中T表示有T个客人，n表示菜被吃过的次数，于是有
1700539506
1700539507
1700539508
．
1700539509
1700539510
（11.9）
1700539511
1700539512
1700539513
1700539514
这就是说是以的概率成立的：
1700539515
1700539516
1700539517
1700539518
1700539519
1700539520
1700539521
当T=2时，成立的概率为0.875； 当T=3时，成立的概率为0.975； 当T=4时，成立的概率为0.992。 可以看到，当Δ取值为时，回报的均值距离真实回报 p的差距在Δ范围内的概率已经非常接近1了，因此Δ的取值是一个非常合适的“置信区间上界”。我们乐观地认为每道菜能够获得的回报是+Δ，既利用到了当前回报的信息，也使用“置信区间上界”进行了探索。
1700539522
1700539523
·总结与扩展·
1700539524
1700539525
如果读者对探索和利用问题有兴趣，可以继续探究一下基于贝叶斯思想的Thompson Sampling，和考虑上下文信息的LinUCB。
1700539526
1700539527
1700539528
1700539529