提出最优后悔率算法，实现通信型马尔可夫决策过程的渐近最优学习。
Asymptotically optimal regret in communicating Markov decision processes
- 通过显式追踪最优常数K(M)，平衡探索、共探索与利用。
- 后悔率达到K(M)log(T)+o(log(T))，为理论最优界。
- 设计正则化机制，从数据中高精度估计不连续的K(M)，适合强化学习研究者。
本文提出一种学习算法，在平均奖励设定下针对通信型马尔可夫决策过程（Markov decision process）实现了渐近最优后悔率。给定通信型马尔可夫决策过程 $M$，该算法的后悔率为 $K(M) imes \log(T) + \mathrm{o}(\log(T))$，其中 $T$ 为学习步数，$K(M)$ 为最优常数。算法通过显式追踪 $K(M)$ 实现最优学习，同时在探索（次优动作以获取信息）、共探索（最优动作以获取信息）和利用（最优动作以最大化得分）之间进行权衡。我们进一步证明 $K(M)$ 是不连续函数，带来实现挑战。为此，提出了一个正则化机制，可从经验数据中任意精度估计 $K(M)$。
原文摘要 · Abstract (English)
In this paper, we present a learning algorithm that achieves asymptotically optimal regret for Markov decision processes in average reward under a communicating assumption. That is, given a communicating Markov decision process $M$, our algorithm has regret $K(M) \log(T) + \mathrm{o}(\log(T))$ where $T$ is the number of learning steps and $K(M)$ is the best possible constant. This algorithm works by explicitly tracking the constant $K(M)$ to learn optimally, then balances the trade-off between exploration (playing sub-optimally to gain information), co-exploration (playing optimally to gain information) and exploitation (playing optimally to score maximally). We further show that the function $K(M)$ is discontinuous, which is a consequence challenge for our approach. To that end, we describe a regularization mechanism to estimate $K(M)$ with arbitrary precision from empirical data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。