多臂老虎机实验中的风险与最优策略

多臂老虎机（Multi-Armed Bandit, MAB）问题是经济学与机器学习交叉领域的核心决策问题，描述决策者如何在多个未知回报的选项中序贯分配资源以最大化累积福利。尽管汤普森抽样（Thompson Sampling, TS）和置信上界（Upper Confidence Bound, UCB）等启发式算法在实践中被广泛使用，但贝叶斯风险与极小化极大风险（minimax risk）的精确刻画以及与之对应的最优策略一直悬而未决。本文在扩散渐近（diffusion asymptotics）框架下，对多臂老虎机实验进行了系统的统计决策分析。在该框架中，不同臂的预期回报差异以极小化极大速率 n^{-1/2} 缩放，先验分布置于缩放后的均值之上以确保其"不可忽略"。作者首先在高斯回报设定下，将最小贝叶斯风险刻画为一个二阶偏微分方程（PDE）即 Hamilton-Jacobi-Bellman 方程的解，并证明该方程可通过有限差分法或蒙特卡洛方法高效求解。进一步，利用实验极限（limit of experiments）方法，作者证明该 PDE 刻画对参数化和非参数化回报分布均渐近成立——任何多臂老虎机问题均可渐近地简化为高斯回报设定。在该简化过程中，渐近充分的状态变量仅为每臂的拉动次数和得分过程（或累积回报），从而将状态空间从 O(n) 大幅压缩至每臂二维。基于 PDE 的数值求解，作者推导了最优贝叶斯和极小化极大策略，并发现最优策略显著优于 TS——后者的贝叶斯风险在某些情境下高达最优策略的两倍。与之相反，适当调参的 MOSS 算法（极小化极大最优随机设定算法）在独立高斯先验下可逼近最优策略。作者进一步将贝叶斯风险框架扩展至极小化极大风险：通过将极小化极大风险视为最不利先验（least favorable prior）下的贝叶斯风险，计算了一臂老虎机的最优极小化极大下界 0.373σ√n。两个基于真实数据（Google Analytics 网站优化实验和 Washington Post 新闻标题选择实验）的实证示例验证了理论结论。