随机规划中的序贯决策与多臂老虎机问题 我将通过以下步骤为您系统讲解这个交叉领域： 基础概念融合 多臂老虎机问题本质上是探索与利用的权衡问题：面对K个收益分布未知的选项（老虎机），决策者需通过序贯选择来最大化累积收益。在随机规划框架下，这被建模为具有不完全信息的序贯决策过程，每个时间步的选择都会带来新的收益观测值，同时更新对收益分布的认知。 2.问题形式化建模 设动作空间A={1,...,K}，每个动作a对应未知收益分布ν_ a。在时刻t： 决策者基于历史观测H_ {t-1}={a_ 1,r_ 1,...,a_ {t-1},r_ {t-1}}选择动作a_ t 获得随机收益r_ t ~ ν_ {a_ t} 目标是最小化T步累积遗憾：R(T)=T·μ^ -Σ_ {t=1}^T E[ r_ t ] 其中μ^ =max_ {a∈A} E_ {r~ν_ a}[ r ]为最优动作的期望收益 3.核心求解算法族 • ε-贪心算法：以1-ε概率选择当前经验最优动作，以ε概率随机探索 • UCB（上置信界）算法：选择具有最大置信上界的动作 a_ t=argmax_ {a∈A}(μ̂_ {a,t-1}+√(2ln t/N_ {a,t-1})) 其中N_ {a,t-1}是动作a的被选次数 • 汤普森采样：通过后验分布进行随机化选择 P(a_ t=a)=P(μ_ a=max_ {a'∈A} μ_ a' | H_ {t-1}) 4.理论性能分析 • 贪心算法可能陷入次优动作（线性遗憾） • UCB算法实现O(log T)的渐近遗憾界 • 汤普森采样对伯努利收益可达贝叶斯遗憾上界O(√{KT log K}) 5.扩展与变体 • 上下文老虎机：在时刻t额外观测上下文x_ t∈R^d • 线性老虎机：期望收益E[ r_ t|a_ t]=〈θ,x_ {a_ t}〉 • 对抗性老虎机：收益由对手自适应生成 6.与随机规划的深度融合 在随机规划的序贯决策框架中，多臂老虎机问题可视为： 状态空间：信念状态（收益分布的后验） 动作空间：有限的选择集合 转移动力学：信念状态的贝叶斯更新 目标函数：有限时域的折扣累积收益 这种形式化使得我们可以运用随机规划中的值迭代、策略迭代等方法求解精确解，同时启发式算法（如UCB）提供了计算可行的近似方案。