多臂老虎机与马尔可夫决策过程:从入门到体系
符号速查表
本表为 k2md 入库时补充的阅读辅助。下方原有正文、公式及 AI 生成标注未改;符号释义不代表对全部结论的核验。
| 符号 | 读法 | 含义 |
|---|---|---|
| N、i、j | 臂的数量、候选臂的索引、求和中的臂索引 | |
| t、T、k | 当前轮次、总轮数、未来奖励的偏移步数;下标零表示初始时刻 | |
| mu 缪,下标 i;mu star;mu hat i | 臂 i 的真实均值、最优臂均值、臂 i 的经验估计;星号表示最优值,帽号表示估计 | |
| r t、R T | 第 t 轮实际奖励、正文用最优期望总奖励减实际总奖励定义的遗憾量;与 MDP 的奖励函数 R 区分 | |
| epsilon 艾普西隆、一减 epsilon | 随机探索概率、按当前估计利用的概率 | |
| P i;tau 陶;e;自然对数 | softmax 选臂概率、温度、自然对数的底、自然对数运算 | |
| q;alpha 阿尔法;beta 贝塔 | 伯努利成功率、Beta 分布的两个形状参数 | |
| s、f、贝塔分布 | Thompson Sampling 中的成功次数、失败次数、使用均匀先验后的后验分布;这里的 s 不表示环境状态 | |
| A t、n i | 第 t 轮选择的臂或动作、臂 i 已被选择的次数 | |
| S、s、S 零、S t、s t、s prime | 状态集合、具体状态、初始或单一状态、时刻 t 的状态、下一状态;正文大小写记法混用,应按公式上下文区分集合与随机变量 | |
| A、a | 动作集合、具体动作 | |
| 给定 s/给定 s 和 a 时到 s prime 的概率 | 马尔可夫链转移概率、MDP 中以动作作为条件的转移概率 | |
| R s、R s a s prime、R t 加一 | 正文中的状态奖励、状态转移奖励、下一步获得的奖励 | |
| gamma 伽马、gamma 的 k 次方 | 折扣因子、未来第 k 项奖励的折扣权重 | |
| G t | 从时刻 t 开始的折扣奖励总和(return);与单步 reward 区分 | |
| pi 派;给定 s 的动作概率;pi s | 策略、随机策略、确定性策略 | |
| V pi、Q pi、Q star | 指定策略的状态价值、动作价值、最优动作价值;上标 pi 表示采用的策略,不是乘方 | |
| 策略 pi 下的条件期望 | 对策略与环境产生的随机性取平均,并以竖线后的条件为前提 | |
| V s、V s prime | 简写的当前状态价值、下一状态价值;具体采用的策略需由语境确定 | |
| h t | RNN 或 Transformer 对历史的表示;正文把它用于解释历史压缩 | |
| O、o、观测条件概率 | 观测集合、具体观测、正文给出的 POMDP 观测模型记法 | |
| 求和、最大值、取得最大值的自变量、平方根 | 聚合与选优算子;argmax 返回臂或动作索引,不是最大分数 | |
| 大 O log T | 对数级渐近增长记法;这里 O 不表示观测集合,具体界需要相应假设 | |
| S 的基数、无穷、给定、趋向、不大于、约等于 | 状态数量、无限求和上限、条件概率分隔符、极限与比较符号 |
本文系统整理多臂老虎机(Multi-Armed Bandit, MAB)、马尔可夫决策过程(Markov Decision Process, MDP)及其扩展家族的核心概念、算法与相互关系。
目录
一、多臂老虎机(MAB)
1.1 问题起源与定义
多臂老虎机问题的名字来自赌场里的"吃角子老虎机"(slot machine)。想象你面前有 N 台老虎机,每台都有一个拉杆(arm),拉下后会按照某个未知的概率分布给出回报。你的目标是:在有限的拉臂次数内,最大化总回报。
核心难点在于:你不知道每台机器的真实回报率,必须通过尝试来获取信息。
用强化学习的语言正式定义:
- 状态(State):单一状态 S₀(非关联的,每次决策不依赖历史状态)
- 动作(Action):选择 N 个摇臂中的一个
- 回报(Reward):拉臂后获得的收益(通常是伯努利 0/1,或高斯连续值)
- 这是一个单状态的马尔可夫决策过程(MDP),也是强化学习最简单的入门问题
与监督学习的关键区别:监督学习告诉你"正确答案是什么"(instructive feedback),而老虎机只告诉你"这次选得好不好"(evaluative feedback)——你永远不知道没选的那个臂会给多少回报。
1.2 核心矛盾:探索 vs 利用
这是整个多臂老虎机问题的灵魂。
| 探索(Exploration) | 利用(Exploitation) | |
|---|---|---|
| 做什么 | 尝试不了解的摇臂,收集信息 | 反复拉当前认为回报最高的摇臂 |
| 目的 | 降低不确定性,发现更优选项 | 最大化即时收益 |
| 代价 | 可能在差的臂上浪费次数 | 可能错过真正最优的臂 |
| 极端结果 | 随机策略:回报低但估计准 | 纯贪婪策略:可能被早期运气误导 |
两者天然冲突:把次数花在探索上,就少了利用的收益;只顾利用,又可能永远困在次优选项里。所有 MAB 算法本质上都是在找这个平衡的最优解。
1.3 评价指标:遗憾值(Regret)
衡量一个 MAB 算法好坏的标准指标是累积遗憾(Cumulative Regret):
其中:
- 是最优臂的真实期望回报
- 是第 t 轮实际获得的回报
- 是总轮数
含义:如果我们"全知全能",每轮都选最优臂,能拿到 ;实际拿到的和这个理论上界的差距就是遗憾。好的算法应该让遗憾随 T 次线性增长(如 ),而不是线性增长。
1.4 经典算法详解
以下结合实验设定说明:3 个摇臂 A/B/C,真实胜率分别为 30%/50%/80%,每轮拉 1000 次,共模拟 2000 轮取平均。
(1)全知全能(Omniscient)—— 理论上界
假设你已经知道 C 臂胜率 80%,那就一直拉 C。
- 平均回报:800(这是所有策略的上界,用来做对比基准)
(2)随机策略(Random)—— 纯探索
每次等概率随机选一个臂。
- 理论回报 = (300 + 500 + 800) / 3 ≈ 533.3
- 实验结果:平均回报 533.44,RMSE 0.0006
- 特点:对每个臂的概率估计极准(RMSE 极低),但回报最差——严重偏探索
(3)贪婪策略(Greedy)—— 纯利用
每个臂先拉一次,然后一直拉初始回报最高的那个。
- 实验结果:平均回报 733.15,RMSE 0.177
- 问题:第一次拉 C 臂可能恰好输了(20% 概率),就会误以为 B 或 A 更好,从此锁死在次优臂上——严重偏利用,估计很不准
(4)ε-贪婪(ε-Greedy)—— 最简单的平衡
设置一个小的 ε(通常 0.1):
-
以 1-ε 的概率:选当前平均回报最高的臂(利用)
-
以 ε 的概率:在所有臂中均匀随机选一个(探索)
-
实验结果:平均回报 763.80,RMSE 0.005
-
特点:简单有效,探索让估计收敛到真实值,利用保证大部分收益——平衡较好
-
缺点:ε 固定意味着即使已经确定了最优臂,仍会持续浪费 ε 的比例去随机探索
(5)Softmax-贪婪(Softmax-Greedy)—— 探索时也带倾向性
与 ε-Greedy 的区别在于:探索时不是均匀随机,而是用 Softmax 函数根据各臂当前估计回报率生成一个概率分布,回报率高的臂被选中的概率更大。
其中 τ 是温度参数。
- 实验结果:平均回报 767.25,RMSE 0.007
- 特点:"探索中不忘利用",回报略高于 ε-Greedy,但估计误差略高
(6)ε-下降(ε-Decreasing)—— 动态调整探索率
核心思想:早期多探索,后期多利用。初始 ε=0.1,随时间线性(或指数)下降到接近 0。
- 实验结果:平均回报 777.42,RMSE 0.008
- 特点:回报更高,但因为后期几乎不探索,对较差臂的估计误差上升
- 这是一个非常符合直觉的策略:"先摸清情况,再专心赚钱"
(7)汤普森采样(Thompson Sampling)—— 贝叶斯概率匹配
这是实验中表现最好的策略,由 William Thompson 于 1933 年提出。
核心思想:为每个臂维护一个胜率的后验概率分布(贝叶斯框架),每轮从每个臂的后验分布中采样一个值,然后选采样值最大的那个臂。
数学推导(伯努利回报):
- 每个臂胜率 q 服从 Beta 分布(伯努利的共轭先验)
- 初始先验:Beta(α=1, β=1)(等价于均匀分布)
- 拉臂后:赢了 α+1,输了 β+1 → 后验变为 Beta(1+s, 1+f)
- 每轮:从每个臂的 Beta(1+s, 1+f) 中采样一个数,选最大的
def thompson_action(success, failure):
samples = np.random.beta(1 + success, 1 + failure)
return np.argmax(samples)
为什么有效:
-
被拉得多、估计准的臂 → Beta 分布尖锐 → 采样值稳定在真实均值附近
-
被拉得少、不确定的臂 → Beta 分布宽 → 偶尔能采样出很高的值,从而获得探索机会
-
不确定性自动转化为探索概率,无需手动调 ε
-
实验结果:平均回报 791.21,RMSE 0.053
-
是所有策略中最接近理论上界 800 的
(8)UCB(Upper Confidence Bound,上置信界)—— 乐观面对未知
UCB 是与 Thompson Sampling 并列的两大经典算法之一。
核心思想:"乐观面对不确定性"——不仅看当前平均回报,还给不确定的臂加上一个信心奖金。
其中:
- 是臂 i 的当前平均回报
- 是臂 i 被拉过的次数
- 是当前总轮数
- 第二项 就是不确定性奖金:拉得越少,奖金越大
特点:
- 有严格的理论遗憾界保证:
- 确定性策略(不像 ε-Greedy 和 Thompson 有随机性)
- 不需要先验分布假设
1.5 算法性能对比汇总
基于实验(3臂,胜率 30%/50%/80%,每轮1000次,2000轮平均):
| 策略 | 平均回报 | RMSE(估计误差) | 偏向 | 核心思想 |
|---|---|---|---|---|
| 全知全能(上界) | 800 | 0 | - | 知道答案 |
| 随机 | 533.44 | 0.0006 | 纯探索 | 完全随机 |
| 贪婪 | 733.15 | 0.177 | 纯利用 | 一次试错后锁死 |
| ε-Greedy | 763.80 | 0.005 | 平衡 | 固定概率随机探索 |
| Softmax-Greedy | 767.25 | 0.007 | 略偏利用 | 探索时倾向高回报臂 |
| ε-Decreasing | 777.42 | 0.008 | 后期偏利用 | 探索率随时间下降 |
| Thompson Sampling | 791.21 | 0.053 | 最优平衡 | 贝叶斯后验采样 |
| UCB1 | — | — | 最优平衡 | 不确定性奖金(理论保证) |
注意:RMSE 低不代表策略好——随机策略 RMSE 最低但回报最差。回报和估计精度之间存在固有权衡。
1.6 实际应用场景
多臂老虎机的思想无处不在:
| 领域 | 应用 | 臂(Action) | 回报(Reward) |
|---|---|---|---|
| 在线广告 | 选择展示哪个广告创意 | 不同广告素材 | 用户是否点击/转化 |
| 推荐系统 | 冷启动阶段探索新内容 | 不同推荐策略/物品 | 用户点击率/停留时长 |
| A/B 测试 | 自适应分配流量 | 不同实验版本 | 转化率 |
| 临床试验 | 自适应分配治疗方案 | 不同药物/疗法 | 患者康复率 |
| 网络路由 | 选择传输路径 | 不同路由 | 延迟/丢包率 |
| LLM 路由 | 选择哪个模型处理请求 | 不同 LLM | 回答质量/成本比 |
与传统 A/B 测试的对比:
- 传统 A/B 测试:先固定分流比例(如 50/50),跑满样本量再分析——探索和利用是分离的两个阶段
- Bandit:探索和利用同时进行,动态把更多流量分配给表现好的版本——减少"浪费"在差版本上的流量
二、马尔可夫决策过程(MDP)
2.1 从马尔可夫链到 MDP:逐层加要素
MDP 不是凭空出现的,它是在更简单的模型上一步步"加东西"得到的。
第 1 层:马尔可夫链(Markov Chain)
最简单的模型,只描述状态之间怎么跳。
- 只有一个要素:状态集合 S 和 转移概率 P(s'|s)
- 核心假设——马尔可夫性:下一个状态只取决于当前状态,与更早的历史无关
- 例子:天气预测(今天晴→明天多云的概率)、网页跳转(PageRank)
- 没有动作,没有奖励——纯描述系统怎么演化
第 2 层:马尔可夫奖励过程(MRP)
在马尔可夫链基础上加奖励。
- 新增:奖励函数 R(s)(进入状态 s 时获得的即时奖励)和 折扣因子 γ
- 引入了**回报(Return)**的概念:从当前状态开始,未来能获得的折扣奖励总和
- γ 的意义:越远的奖励越不重要;γ→0 短视,γ→1 远视
- 还是没有动作——你只能旁观系统演化并算奖励,不能干预
第 3 层:马尔可夫决策过程(MDP)
在 MRP 基础上加动作——这是强化学习的标准框架。
- 新增:动作集合 A,转移概率变成 P(s'|s, a)(在状态 s 下执行动作 a 后跳到 s' 的概率),奖励变成 R(s, a, s')
- 现在你可以做决策了:在每个状态选择一个动作,影响系统往哪走
- 目标:找到一个策略 π(a|s)(在状态 s 下选动作 a 的概率),最大化期望累积折扣奖励
2.2 MDP 的五元组与核心概念
一个 MDP 由五个要素定义,记为 (S, A, P, R, γ):
| 符号 | 名称 | 含义 | 例子(网格世界) |
|---|---|---|---|
| S | 状态集合 | 智能体可能处于的所有情况 | 网格中的每个格子坐标 |
| A | 动作集合 | 智能体能做的所有选择 | 上/下/左/右移动 |
| P | 转移概率 | P(s'|s,a):在 s 做 a 后到 s' 的概率 | 80% 按方向走,20% 打滑 |
| R | 奖励函数 | R(s,a,s'):转移后获得的即时奖励 | 到达终点 +1,撞墙 -0.1 |
| γ | 折扣因子 | 未来奖励的衰减系数(0≤γ≤1) | γ=0.9 表示一步远的奖励打 9 折 |
关键派生概念
1. 策略(Policy)π
- 一个从状态到动作的映射:π(a|s) = 在状态 s 下选择动作 a 的概率
- 确定性策略:π(s) = a(每个状态只选一个动作)
- 随机性策略:π(a|s) 是一个概率分布
2. 状态价值函数 V^π(s)
- 从状态 s 出发,按照策略 π 走,能获得的期望回报
- 回答:"我现在在 s,按 π 走,未来能赚多少?"
3. 动作价值函数 Q^π(s, a)
- 在状态 s 下先执行动作 a,之后按策略 π 走,能获得的期望回报
- 回答:"我在 s,先做 a,之后按 π 走,能赚多少?"
- Q 函数是强化学习最核心的量——知道了 Q*,最优策略就是 argmax_a Q*(s,a)
4. 贝尔曼方程(Bellman Equation)
- 价值函数的递归分解,把"当前奖励"和"未来价值"拆开:
- 这是所有动态规划和强化学习算法的数学基础
2.3 单状态 MDP = 多臂老虎机
单状态 MDP,顾名思义,就是状态集合里只有一个状态(|S|=1)的 MDP。
| MDP 要素 | 一般 MDP | 单状态 MDP |
|---|---|---|
| 状态 S | 多个状态 | 只有 1 个状态 S₀ |
| 动作 A | 多个动作 | 多个动作(= 选哪个臂) |
| 转移 P(s'|s,a) | 动作改变下一状态 | 永远回到 S₀(无状态变化) |
| 奖励 R(s,a,s') | 依赖状态和动作 | 只依赖动作(每个臂有自己的回报分布) |
| 策略 π(a|s) | 依赖状态 | 与状态无关(固定的选臂策略) |
结论:单状态 MDP = 多臂老虎机(Multi-Armed Bandit)
- 每次决策都在同一个"情境"下,你的动作(选臂)不会改变未来的情境
- 没有"状态转移"需要学习,只需要学习每个动作的价值
- 这就是为什么 MAB 是强化学习最简单的入门问题——它剥离了"状态"这个复杂维度,只保留探索 vs 利用这一个核心矛盾
用一句话说:MDP 是"在不同情境下做不同决策",单状态 MDP 是"在同一个情境下反复做决策"。
2.4 中间形态:Contextual Bandit
**上下文老虎机(Contextual Bandit)**是介于 MAB 和完整 MDP 之间的重要形态,工业界用得极多:
- 有多个状态(每个用户/情境是一个状态)
- 但动作不会改变下一状态——你给用户推了一篇文章,不会改变这个用户是谁
- 每轮观察到一个上下文(用户特征),然后选一个动作(推什么内容),获得奖励(点没点击)
- 比 MAB 多了"因情境而异"的能力,比完整 MDP 少了"长期规划"的复杂度
三者对比:
| 模型 | 状态数 | 动作影响下一状态? | 核心问题 |
|---|---|---|---|
| 多臂老虎机(MAB) | 1 | 否 | 探索 vs 利用 |
| 上下文老虎机 | 多 | 否 | 不同情境选不同动作 + 探索 |
| 完整 MDP | 多 | 是 | 长期规划 + 信用分配 + 探索 |
三、马尔可夫性深度解析
3.1 公式拆解
| 部分 | 含义 |
|---|---|
| 当前时刻 t 的状态 | |
| 从开始到上一刻的全部历史状态 | |
| 左边 | 知道完整历史时,下一时刻状态的概率分布 |
| 右边 | 只知道当前状态时,下一时刻状态的概率分布 |
| 等号 | 两者相等 |
3.2 通俗理解与例子
一句话翻译:
"未来只取决于现在,不取决于过去。"
或者更精确地说:只要知道了当前状态 ,那么更早的历史()对于预测下一状态 就没有任何额外信息了。
满足马尔可夫性的例子:棋盘游戏
假设状态是"当前棋盘上所有棋子的位置"。
- 你知道现在的棋盘局面 → 就能判断下一步各种走法的概率
- 你不需要知道这盘棋是怎么走到现在这个局面的(是 10 步走到的还是 50 步走到的、中间有没有悔棋)——这些历史信息对"下一步怎么走"没有影响
这就是马尔可夫性:当前状态已经包含了所有对未来有用的信息。
不满足马尔可夫性的例子:生病吃药
假设状态是"今天有没有发烧"。
- 只知道"今天发烧",不知道"已经连续发烧 5 天了"还是"第一天发烧"
- 这两种情况"明天退烧的概率"显然不一样
- 所以"今天是否发烧"这个状态不满足马尔可夫性——历史(连续发烧几天)确实携带了额外信息
- 解决办法:把状态定义扩充为"连续发烧天数 + 今天体温",这样就满足马尔可夫性了
3.3 为什么这个假设重要?
马尔可夫性是一个极强的简化假设,它带来了三个关键好处:
1. 计算上的巨大简化
没有马尔可夫性,预测未来需要考虑整个历史序列,计算量随时间指数增长。有了马尔可夫性,只需要看当前一个状态,计算量恒定。
2. 可以用"状态"作为充分统计量
状态 是对历史的压缩——它把所有对未来有用的信息都编码进去了。这就是为什么在 MDP 里我们只讨论"在状态 s 下做什么",而不用讨论"在历史 h 下做什么"。
3. 贝尔曼方程成立的前提
价值函数递归:
之所以能成立,就是因为"从 s 出发的未来"和"怎么走到 s 的"无关——这正是马尔可夫性保证的。
3.4 现实中不满足怎么办?
真实世界很多问题不天然满足马尔可夫性,常见的处理办法:
- 扩充状态定义:把历史中有用的信息加进状态里(比如"连续发烧天数")
- 用 POMDP:承认状态观测不全,用"信念状态"(对可能状态的概率分布)来代替真实状态——信念状态本身是满足马尔可夫性的
- 用 RNN/Transformer:在深度学习里,隐藏状态 就是对历史的压缩,扮演了马尔可夫状态的角色
一个常见的误解:很多人以为马尔可夫性是说"历史不重要",这是错的。正确的理解是:历史的影响已经全部被压缩进了当前状态里。比如下棋,你前 50 步怎么走的当然重要——它决定了现在的棋盘局面。但一旦局面确定了,你就不需要再回忆前 50 步了,因为所有信息都在棋盘上。
四、MDP 的扩展家族
标准 MDP 是一个理想化的框架,真实世界的问题往往需要在它基础上做扩展。
4.1 POMDP(部分可观测 MDP)
- 问题:标准 MDP 假设智能体能看到完整状态,但现实中你往往只能看到部分信息
- 例子:打牌时你看不到对手的牌;自动驾驶中传感器有盲区
- 新增要素:观测集合 O 和观测概率 P(o|s,a)
- 智能体需要根据历史观测推断自己可能在什么状态(维护一个"信念状态")
- 比 MDP 难得多,但更接近真实世界
4.2 多智能体 MDP
- 问题:标准 MDP 只有一个决策者,但很多场景有多个智能体同时行动
- 例子:多机器人协作、自动驾驶车队、游戏 AI、竞价广告
- 每个智能体有自己的动作和奖励,联合动作决定状态转移
- 挑战:非平稳环境(其他智能体也在学习)、信用分配、协作 vs 竞争
4.3 SMDP(半马尔可夫决策过程)
- 问题:标准 MDP 假设每个动作在一个时间步内完成,但有些动作需要持续可变的时间
- 例子:机器人"走到门口"需要 5 秒,"抓取物体"需要 2 秒
- 状态转移发生在随机的时间点,动作有持续时间
- 是分层强化学习(Hierarchical RL)和"选项框架"(Options Framework)的数学基础——把一系列低级动作打包成一个"选项",在 SMDP 层面学习
4.4 CMDP(约束 MDP)
- 问题:标准 MDP 只优化总奖励,但现实中还有安全、成本、伦理等约束
- 例子:机器人不能撞人(安全约束)、广告投放不能超预算(成本约束)
- 除了最大化奖励,还要求某些累积成本不超过阈值
- 解法通常用拉格朗日乘子法,把约束转化为惩罚项
4.5 平均奖励 MDP
- 问题:标准 MDP 用折扣奖励,但对于持续运行的系统(如通信网络、服务器调度),"无限远的未来"也很重要
- 优化目标是长期平均每步奖励,而不是折扣总和
- 没有 γ,需要处理"偏差项"(differential reward)
4.6 鲁棒 MDP
- 问题:标准 MDP 假设转移概率 P 已知且固定,但现实中模型可能不准或环境会变
- 转移概率在一个不确定集合内波动,要求策略在最坏情况下仍最优
- 适用于安全关键场景(医疗、自动驾驶、金融)
五、MDP 与强化学习的关系
最后理清一个常见的困惑:MDP 是问题模型,强化学习是解法。
- MDP 是对"序贯决策问题"的数学建模——它定义了问题长什么样,但不告诉你怎么解
- 动态规划(DP):当 MDP 的 P 和 R 完全已知时,用值迭代/策略迭代精确求解(需要遍历所有状态)
- 强化学习(RL):当 P 和 R 未知时,智能体通过与环境交互(试错)来学习最优策略——这就是探索 vs 利用的来源
- 多臂老虎机是 RL 中最简单的情形(单状态),完整 MDP 下的 RL 算法(Q-learning、Policy Gradient、DQN、PPO 等)则要同时处理状态泛化、信用分配和探索
六、一句话总结
马尔可夫链描述"世界怎么变",MRP 加上"变化带来多少奖励",MDP 再加上"你可以干预世界";单状态 MDP 就是多臂老虎机,上下文老虎机是多状态但无长期影响的中间态,POMDP/多智能体/SMDP/CMDP 则是为了应对真实世界的各种复杂性而做的扩展。
各算法哲学:随机——全都试试,不偏不倚;贪婪——相信第一印象,一条路走到黑;ε-Greedy——大部分时间听经验,偶尔碰碰运气;Softmax-Greedy——碰运气时也优先挑看起来不错的;ε-Decreasing——年轻时多闯荡,年纪大了专心搞钱;UCB——对未知保持乐观,给不确定性发奖金;Thompson Sampling——用概率分布模拟世界,让不确定性自己决定探索多少。
本文基于多臂老虎机与马尔可夫决策过程的经典教材与公开技术资料整理。 #(注:内容由AI生成)