随机规划中的序贯决策与多臂老虎机问题
字数 1318 2025-11-12 18:35:17

随机规划中的序贯决策与多臂老虎机问题

  1. 问题背景与基本定义
    多臂老虎机问题（Multi-Armed Bandit, MAB）是序贯决策的经典模型，其核心思想是代理在多个动作（如“老虎机臂”）间进行选择，每个动作的奖励服从未知分布。目标是通过多次试验最大化累积奖励。在随机规划中，MAB被形式化为一个探索与利用的权衡问题：探索未知动作以获取信息，或利用当前已知高奖励动作。

  2. 数学建模与目标函数
    假设有 \(K\) 个动作（臂），每个动作 \(i\) 的奖励服从分布 \(\nu_i\)，均值为 \(\mu_i\)。在时间 \(t=1,2,\dots,T\)，代理选择动作 \(a_t \in \{1,\dots,K\}\)，观察到独立同分布的奖励 \(r_t \sim \nu_{a_t}\)。目标是最大化期望累积奖励：

\[ \mathbb{E}\left[\sum_{t=1}^T r_t\right] \]

等价于最小化遗憾（Regret），即与始终选择最优动作的累积奖励差：

\[ R(T) = T\mu^* - \mathbb{E}\left[\sum_{t=1}^T r_t\right] \]

其中 \(\mu^* = \max_i \mu_i\)。

  1. 经典算法：置信上界与汤普森采样
    • 置信上界算法：为每个动作计算奖励均值的置信区间，选择上界最大的动作。具体步骤：
  2. 初始化每个动作的尝试次数 \(n_i=0\) 和累积奖励 \(S_i=0\)。
  3. 在每轮 \(t\)，计算每个动作的UCB：

\[ \text{UCB}_i = \frac{S_i}{n_i} + \sqrt{\frac{2\ln t}{n_i}} \]

  1. 选择 \(\text{UCB}_i\) 最大的动作，更新 \(n_i\) 和 \(S_i\)。
  • 汤普森采样：基于贝叶斯思想，从每个动作奖励分布的后验分布中采样，选择采样值最大的动作。以伯努利奖励为例：

  1. 初始化每个动作的先验分布为 \(\text{Beta}(1,1)\)。

  2. 每轮从每个动作的后验分布中采样一个值 \(\theta_i\)，选择 \(\theta_i\) 最大的动作。
    3. 根据观测到的奖励更新后验分布参数。

  3. 与随机规划的关联
    MAB是随机规划中序贯决策的特例，其特点在于：

    • 信息演化：每轮动作影响后续奖励分布的认知。
    • 自适应策略：决策依赖历史观测，需动态调整探索与利用的平衡。
    • 随机优化视角：MAB可视为一个部分可观测马尔可夫决策过程（POMDP）的简化形式。

  4. 扩展模型与前沿方向

    • 上下文老虎机：动作奖励与上下文信息（如用户特征）相关，需结合线性模型或神经网络。
    • 对抗性老虎机：奖励由对手生成，需采用指数权重算法（如Exp3）。
    • 约束优化：在资源分配、临床试验等场景中，需满足额外约束（如安全边界、预算限制）。

  5. 实际应用示例

    • 在线广告投放：将广告位视为“臂”，通过MAB优化点击率。
    • 自适应临床试验：将治疗方案作为臂，动态分配患者以最大化疗效。
    • 网络路由选择：在多个路径中选择延迟最低的通信路径。
随机规划中的序贯决策与多臂老虎机问题 问题背景与基本定义 多臂老虎机问题（Multi-Armed Bandit, MAB）是序贯决策的经典模型，其核心思想是代理在多个动作（如“老虎机臂”）间进行选择，每个动作的奖励服从未知分布。目标是通过多次试验最大化累积奖励。在随机规划中，MAB被形式化为一个 探索与利用的权衡问题 ：探索未知动作以获取信息，或利用当前已知高奖励动作。 数学建模与目标函数 假设有 \(K\) 个动作（臂），每个动作 \(i\) 的奖励服从分布 \(\nu_ i\)，均值为 \(\mu_ i\)。在时间 \(t=1,2,\dots,T\)，代理选择动作 \(a_ t \in \{1,\dots,K\}\)，观察到独立同分布的奖励 \(r_ t \sim \nu_ {a_ t}\)。目标是最大化期望累积奖励： \[ \mathbb{E}\left[ \sum_ {t=1}^T r_ t\right ] \] 等价于最小化 遗憾 （Regret），即与始终选择最优动作的累积奖励差： \[ R(T) = T\mu^* - \mathbb{E}\left[ \sum_ {t=1}^T r_ t\right ] \] 其中 \(\mu^* = \max_ i \mu_ i\)。 经典算法：置信上界与汤普森采样 置信上界算法 ：为每个动作计算奖励均值的置信区间，选择上界最大的动作。具体步骤： 初始化每个动作的尝试次数 \(n_ i=0\) 和累积奖励 \(S_ i=0\)。 在每轮 \(t\)，计算每个动作的UCB： \[ \text{UCB}_ i = \frac{S_ i}{n_ i} + \sqrt{\frac{2\ln t}{n_ i}} \] 选择 \(\text{UCB}_ i\) 最大的动作，更新 \(n_ i\) 和 \(S_ i\)。 汤普森采样 ：基于贝叶斯思想，从每个动作奖励分布的后验分布中采样，选择采样值最大的动作。以伯努利奖励为例： 初始化每个动作的先验分布为 \(\text{Beta}(1,1)\)。 每轮从每个动作的后验分布中采样一个值 \(\theta_ i\)，选择 \(\theta_ i\) 最大的动作。 根据观测到的奖励更新后验分布参数。 与随机规划的关联 MAB是随机规划中 序贯决策 的特例，其特点在于： 信息演化 ：每轮动作影响后续奖励分布的认知。 自适应策略 ：决策依赖历史观测，需动态调整探索与利用的平衡。 随机优化视角 ：MAB可视为一个部分可观测马尔可夫决策过程（POMDP）的简化形式。 扩展模型与前沿方向 上下文老虎机 ：动作奖励与上下文信息（如用户特征）相关，需结合线性模型或神经网络。 对抗性老虎机 ：奖励由对手生成，需采用指数权重算法（如Exp3）。 约束优化 ：在资源分配、临床试验等场景中，需满足额外约束（如安全边界、预算限制）。 实际应用示例 在线广告投放 ：将广告位视为“臂”，通过MAB优化点击率。 自适应临床试验 ：将治疗方案作为臂，动态分配患者以最大化疗效。 网络路由选择 ：在多个路径中选择延迟最低的通信路径。