Generalization and Exploration via Randomized Value Functions
Ian Osband Benjamin Van Roy Zheng Wen Stanford University
Abstract
We propose randomized least-squares value iteration (RLSVI) – a new reinforcement learning algorithm designed to explore and generalize efficiently via linearly parameterized value functions. We explain why versions of least-squares value iteration that use Boltzmann or $\epsilon$ -greedy exploration can be highly inefficient, and we present computational results that demonstrate dramatic efficiency gains enjoyed by RLSVI. Further, we establish an upper bound on the expected regret of RLSVI that demonstrates near-optimality in a tabula rasa learning context. More broadly, our results suggest that randomized value functions offer a promising approach to tackling a critical challenge in reinforcement learning: synthesizing efficient exploration and effective generalization.
中文速览
随机化的最小二乘值迭代（Randomized Least-Squares Value Iteration, RLSVI）针对的是强化学习中"探索与泛化如何同时做好"这一核心难题——传统的ε-贪心或Boltzmann探索策略在面对大状态空间时，所需学习时间会随状态数指数级增长，根本无法高效工作。RLSVI的解决思路是：不再随机抖动动作，而是每轮从统计上合理的值函数分布中随机采样一个值函数，然后对该值函数贪婪执行，从而在保持线性参数化泛化能力的同时，实现有方向的系统性探索——这一理念源自Thompson采样。理论分析证明，RLSVI在表格设置（tabular setting）下的期望累积遗憾上界为$\tilde{O}(\sqrt{H^3 SAT})$，不仅与已知下界仅差对数因子，还优于现有最先进乐观算法的$\tilde{O}(\sqrt{H^3 S^2 AT})$界；计算实验也进一步验证了其相对于传统抖动方法的显著效率提升。这项工作的重要性在于，它首次给出了一个既有可证明高效性保障、又能通过线性值函数进行泛化的实用强化学习算法，为大规模状态空间下的高效探索提供了新的理论与实践路径。
原文 arXiv:1402.0635;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1402.0635v3