Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning
Ronan Fruit Matteo Pirotta Alessandro Lazaric Ronald Ortner
Abstract
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound $c$ on the span of the optimal bias function is known. For an MDP with $S$ states, $A$ actions and $\Gamma\leq S$ possible next states, we prove a regret bound of $\widetilde{O}(c\sqrt{\Gamma SAT})$ , which significantly improves over existing algorithms (e.g., UCRL and PSRL), whose regret scales linearly with the MDP diameter $D$ . In fact, the optimal bias span is finite and often much smaller than $D$ (e.g., $D=\infty$ in non-communicating MDPs). A similar result was originally derived by Bartlett and Tewari (2009) for Regal.C, for which no tractable algorithm is available. In this paper, we relax the optimization problem at the core of Regal.C, we carefully analyze its properties, and we provide the first computationally efficient algorithm to solve it. Finally, we report numerical simulations supporting our theoretical findings and showing how SCAL significantly outperforms UCRL in MDPs with large diameter and small span.
中文速览
强化学习在未知环境中探索时，传统算法（如UCRL）的遗憾（regret）上界依赖MDP直径D，但D在许多实际问题中可以无穷大，导致算法性能很差。针对这一问题，作者提出了SCAL算法，核心思路是用最优偏差函数（optimal bias function）的跨度（span）c替代直径D来衡量问题难度——c更能刻画"坏状态"与"好状态"之间的实际代价差距，且往往远小于D。算法的关键在于设计了一个带跨度约束的优化问题，并给出了首个可高效计算的求解器ScOpt，从而将Regal.C这一理论上有效但此前无法实际运行的算法真正落地。理论上SCAL的遗憾上界为$\widetilde{O}(c\sqrt{\Gamma SAT})$，在D远大于c的MDP上显著优于UCRL，数值实验也验证了这一优势；更重要的是，这项工作首次为弱连通MDP提供了兼具理论保证与计算可行性的探索-利用算法。
原文 arXiv:1802.04020;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1802.04020v2