Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
This work addresses the problem of efficient learning in adversarial environments for researchers in reinforcement learning, offering incremental algorithmic improvements with concrete performance gains.
The paper tackles online reinforcement learning in adversarial linear MDPs with bandit feedback, achieving improved regret bounds: an inefficient algorithm attains optimal $\widetilde{\mathcal{O}}(\sqrt{K})$ regret, and an efficient one achieves $\widetilde{\mathcal{O}}(K^{3/4})$ regret, outperforming prior state-of-the-art results.
We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on transitions or access to simulators. We introduce two algorithms that achieve improved regret performance compared to existing approaches. The first algorithm, although computationally inefficient, ensures a regret of $\widetilde{\mathcal{O}}\left(\sqrt{K}\right)$, where $K$ is the number of episodes. This is the first result with the optimal $K$ dependence in the considered setting. The second algorithm, which is based on the policy optimization framework, guarantees a regret of $\widetilde{\mathcal{O}}\left(K^{\frac{3}{4}} \right)$ and is computationally efficient. Both our results significantly improve over the state-of-the-art: a computationally inefficient algorithm by Kong et al. [2023] with $\widetilde{\mathcal{O}}\left(K^{\frac{4}{5}}+poly\left(\frac{1}{λ_{\min}}\right) \right)$ regret, for some problem-dependent constant $λ_{\min}$ that can be arbitrarily close to zero, and a computationally efficient algorithm by Sherman et al. [2023b] with $\widetilde{\mathcal{O}}\left(K^{\frac{6}{7}} \right)$ regret.