We study regret minimization for reinforcement learning (RL) in Latent Markov
Decision Processes (LMDPs) with context in hindsight. We design a novel
model-based algorithmic framework which can be instantiated with both a
model-optimistic and a value-optimistic solver. We prove an
$\widetilde{O}\left(\sqrt{M \Gamma S A K}\right)$ regret bound where $M$ is the
number of contexts, $S$ is the number of states, $A$ is the number of actions,
$K$ is the number of episodes, and $\Gamma \le S$ is the maximum transition
degree of any state-action pair. The regret bound only scales logarithmically
with the planning horizon, thus yielding the first (nearly) horizon-free regret
bound for LMDP. Key in our proof is an analysis of the total variance of alpha
vectors, which is carefully bounded by a recursion-based technique. We
complement our positive result with a novel $\Omega\left(\sqrt{M S A K}\right)$
regret lower bound with $\Gamma = 2$, which shows our upper bound minimax
optimal when $\Gamma$ is a constant. Our lower bound relies on new
constructions of hard instances and an argument based on the symmetrization
technique from theoretical computer science, both of which are technically
different from existing lower bound proof for MDPs, and thus can be of
independent interest.

本文研究基于后知的上下文中的潜在马尔可夫决策过程（LMDPs）的强化学习中的遗憾最小化问题，设计了一种新的基于模型的算法框架，证明了具有一定时间复杂度的遗憾上限。