Large Scale Markov Decision Processes with Changing Rewards

Abstract

We consider Markov Decision Processes (MDPs) where the rewards are unknown and may change in an adversarial manner. We provide an algorithm that achieves state-of-the-art regret bound of $O(\sqrt{\tau (\ln |S|+\ln |A|)T}\ln (T))$, where $S$ is the state space, $A$ is the action space, $\tau$ is the mixing time of the MDP, and $T$ is the number of periods. The algorithm's computational complexity is polynomial in $|S|$ and $|A|$ per period. We then consider a setting often encountered in practice, where the state space of the MDP is too large to allow for exact solutions. By approximating the state-action occupancy measures with a linear architecture of dimension $d\ll |S|$, we propose a modified algorithm with computational complexity polynomial in $d$. We also prove a regret bound for this modified algorithm, which to the best of our knowledge this is the first $\tilde{O}(\sqrt{T})$ regret bound for large scale MDPs with changing rewards.

References in corpus (7)

• A unified view of entropy-regularized Markov decision processes
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Linear Programming for Large-Scale Markov Decision Problems
• A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitions
• An optimal algorithm for stochastic strongly-convex optimization
• Large-Scale Markov Decision Problems via the Linear Programming Dual
• Online Markov decision processes with policy iteration