将策略视为老虎机臂，实现树状MDP的在线学习。
On-line Learning in Tree MDPs by Treating Policies as Bandit Arms
- 把每个策略当作老虎机臂，用带共享数据的信心边界克服指数级策略数难题。
- 样本复杂度和后悔上界按终止状态的差距项求和，优于按每个策略计算。
- 适合研究具有完美回忆的序贯博弈或在线决策场景的开发者。
树状马尔可夫决策过程（T-MDP）是有限时域MDP的一种，从初始状态 $s_{1}$ 出发，每个状态仅通过唯一的状态-动作轨迹可达。这类问题自然出现在具有完美回忆的序贯博弈中，且对手为静态策略。本文研究T-MDP中的在线学习，涵盖PAC学习与最小化后悔两种框架。我们发现，经典老虎机算法—— extsc{Lucb} 和 extsc{Ucb}——可通过将每个策略视为一个臂来应用。该方法的关键技术挑战在于策略数量随状态数呈指数增长。我们的主要创新在于设计基于策略间共享数据的信心边界，使算法可在多项式内存和每步计算时间内实现。我们得到了实例相关的样本复杂度与后悔上界，其形式为所有终止状态的“间隙项”之和，而非每个策略的间隙项。实验表明，该算法在一系列隐信息博弈任务中持续优于现有方法。
原文摘要 · Abstract (English)
A Tree Markov Decision Problem (T-MDP) is a finite-horizon MDP with a starting state $s_{1}$, in which every state is reachable from $s_{1}$ through exactly one state-action trajectory. T-MDPs arise naturally as abstractions of decision making in sequential games with perfect recall, against stationary opponents. We consider the problem of on-line learning in T-MDPs, both in the PAC and the regret-minimisation regimes. We show that well-known bandit algorithms -- \textsc{Lucb} and \textsc{Ucb} -- can be applied on T-MDPs by treating each policy as an arm. The apparent technical challenge in this approach is that the number of policies is exponential in the number of states. Our main innovation is in the design of confidence bounds based on data shared by the policies, so that the bandit algorithms can yet be implemented with polynomial memory and per-step computation. We obtain instance-dependent upper bounds on sample complexity and regret that sum a ``gap term'' from every terminal state, rather than every policy. Empirically, our algorithms consistently outperform available alternatives on a suite of hidden-information games.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。