  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
$\tilde{O}(\sqrt{\mathsf{Var}^\star M \Gamma S A K})$ regret bound where
$\tilde{O}$ hides logarithm factors, $M$ is the number of contexts, $S$ is the
number of states, $A$ is the number of actions, $K$ is the number of episodes,
$\Gamma \le S$ is the maximum transition degree of any state-action pair, and
$\mathsf{Var}^\star$ is a variance quantity describing the determinism of the
LMDP. The regret bound only scales logarithmically with the planning horizon,
thus yielding the first (nearly) horizon-free regret bound for LMDP. This is
also the first problem-dependent regret bound for LMDP. Key in our proof is an
analysis of the total variance of alpha vectors (a generalization of value
functions), which is handled with a truncation method. We complement our
positive result with a novel $\Omega(\sqrt{\mathsf{Var}^\star M S A K})$ regret
lower bound with $\Gamma = 2$, which shows our upper bound minimax optimal when
$\Gamma$ is a constant for the class of variance-bounded LMDPs. Our lower bound
relies on new constructions of hard instances and an argument inspired by 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.
