A Monte Carlo AIXI Approximation
Joel Veness, Kee Siong Ng, Marcus Hutter, William Uther, David Silver
cs.AI, cs.IT, cs.LG
2009-09-04
用广义 UCT 算法 ρUCT 近似有限视野 expectimax、用分解动作条件上下文树 FAC-CTW 近似 Solomonoff 混合，做成首个可运行 AIXI；九个 POMDP 上匹配或超过 U-Tree 与 Active-LZ，Extended Tiger 平均回报 3.97，对照 1-ply 规划的 -0.97。
AIXI 是 Hutter 给未知环境里的通用强化学习写下的贝叶斯最优解。环境被当成未知但可计算的函数，智能体用 Solomonoff 先验对所有图灵机做混合预测，再对有限视野做 expectimax 选动作。多种技术意义上它是最优的，却只渐近可计算，写得出跑不了。此前一直不清楚这套理论能不能指导实际算法，还是只能当原则挂着。
这篇给出第一个计算上可行的直接近似，叫 MC-AIXI（fac-ctw）。规划侧把 UCT 搬到「历史当状态」的设定去逼 expectimax，学习侧把上下文树加权（CTW）做成面向智能体的动作条件版本，去逼 Solomonoff 混合。实验放在一组带噪声、部分可观测的 POMDP 上。
AIXI 那一行公式拆成两块，都要近似。
规划这块，朴素 expectimax 的时间是动作×感知空间的视野次方，视野稍大就炸。他们把 Kocsis 与 Szepesvári 的 UCT 从 MDP 搬出来，用完整交互历史替换状态，得到 ρUCT。树上交错两种节点：决策节点做 max，机会节点按环境模型 ρ 采样下一感知再求和。选动作用 UCB，叶子用均匀随机 rollout 估剩余回报。模拟次数趋向无穷时，树收敛到完整 expectimax，次优动作的概率趋向 0。贝叶斯混合本身也满足环境模型的定义，所以 ρ 可以直接换成混合分布。模型不确定会进规划，信息搜集动作会在视野够把收益兑现时自动出现。
学习这块不能真去混合所有图灵机。FAC-CTW 把 Willems 等人的 CTW 做成动作条件，再按感知的每一个比特拆开。模型类是深度不超过 D 的预测后缀树，一种可变阶 Markov 模型；先验来自树结构的前缀编码，大树罚得更重，是 Ockham 先验。深度 D 的 PST 有 2^{2^D} 棵，朴素混合是双重指数，加权上下文树用 O(D) 维护全体。FAC-CTW 每位一棵树，更新时间 O(D log(|O||R|))，不随历史长度 t 增长，所以能在线跑上百万步。ρUCT 模拟结束后按相反顺序撤销更新，不必拷整棵树。
两者合在一起：每步用当前混合 Υ 当 ρ 跑 ρUCT，按探索策略发动作，收到感知再更新 Υ。若真实环境是平稳、遍历的 n-Markov，值函数均方误差按 O(log b / b) 收敛，策略序列对这类环境自优化。完整贝叶斯探索在有用视野下仍然算不动，实现里加了衰减 ε-greedy。
对照是当时的两条模型基通用 RL：U-Tree 和 Active-LZ。学习阶段强制探索攒模型，评估阶段关掉探索跑 5000 步，报每步平均回报。机器是双路 2.53GHz Xeon、24GB 内存。
MC-AIXI 在三条算法都能跑的域上匹配或超过两条基线。Active-LZ 随经验稳步涨，但更慢；TicTacToe 观测空间太大，它按符号枚举感知，这篇没报它的数。U-Tree 多数域不错，分裂检测开销大，长跑会缺数据点。MC-AIXI 和 Active-LZ 每步时间不随 t 涨。
他们列出评估阶段逼近最优所需的资源：
| 域 | 经验 | 模拟次数 | 每步搜索 |
| 1d Maze | 5×10³ | 250 | 0.1s |
| Cheese Maze | 2.5×10³ | 500 | 0.5s |
| Tiger | 2.5×10⁴ | 25000 | 10.6s |
| Extended Tiger | 5×10⁴ | 25000 | 12.6s |
| 4×4 Grid | 2.5×10⁴ | 500 | 0.3s |
| TicTacToe | 5×10⁵ | 2500 | 4.1s |
| Biased RPS | 1×10⁴ | 5000 | 2.5s |
| Kuhn Poker | 5×10⁶ | 250 | 0.1s |
多数域大约 1000 次模拟就够用。Tiger 和 Extended Tiger 要先听再开门，模拟次数拉到 25000。
把 ρUCT 换成同样预算的 1-ply rollout，Extended Tiger 平均回报从 3.97 掉到 -0.97。Cheese Maze 是 1.28 对 1.25，Biased RPS 是 0.25 对 0.20，其余几乎打平。Kuhn Poker 拿到 0.06，对照二号位对 Nash 一号位的理论上限 1/18≈0.056，已经贴顶。
部分可观测 Pacman 是压力测试：17×17 迷宫，底层状态约 10^{60}，最优策略未知。智能体只看到墙配置、鬼的视线、食物气味等十几比特。在线平均回报从大约 -14 往上走；关掉探索后，经验与模拟次数一起加，每步平均回报能到 0 附近甚至略正。可视化里它学会了不撞墙、找食物、躲鬼，还没学会吃到能量丸后主动追鬼。
这是「AIXI 能不能指导实际算法」的第一次肯定回答。通用智能体在这里没有走深度学习，用的是压缩界的上下文树加 MCTS，2010 年的工作站就能跑。对现在做 model-based RL 和 MCTS 规划的人，有三点仍能用：历史当充分统计量，UCT 就能离开 MDP 盒子；贝叶斯混合可以直接当生成模型塞进搜索；Ockham 先验让可变阶模型不必等所有上下文都挤满数据。
接不了图像或语言。模型类是有界 PST，环境一旦不是平稳 n-Markov，保证就停。当作通用智能体的最小可运行内核可以看，当作现在的 agent 方案不行。
论文自己点了两条。模型类太窄：真实环境若不能被有界深度 PST 预测，表现会差；PST 一大，经验量会炸。作者明确说别指望这套近似处理真实图像或音频。第二条，完整贝叶斯探索/利用除非视野小到不现实，否则算力扛不住，实践里还是启发式。测试域上这没挡住它们摸到最优，更大的问题可能不够。
另外几处读下来要打折。自优化定理写在可数的平稳遍历 n-Markov 上，KT 估计量对应的是不可数混合，作者自己说论证不完全严格，靠离散化来圆。U-Tree 是框架不是死算法，分裂准则、回溯步数、p 值都是这篇自己调的，对照公平性有限。测试域大多很小，1-ply 和 ρUCT 在多数域打平，作者也承认这组题里多步规划不如学准模型重要，Extended Tiger 是少数反例。Pacman 没有最优基线，也没有跟知道真模型的规划器比，「学到了概念」来自可视化，不是量化指标。