Online Convex Optimization in Adversarial Markov Decision Processes
This work addresses online optimization in adversarial MDPs for reinforcement learning applications, offering improved regret bounds and handling convex performance criteria.
The paper tackles the problem of online learning in adversarial Markov decision processes with unknown transitions and arbitrarily changing losses, achieving a regret bound of $ ilde{O}(L|X|\sqrt{|A|T})$ using an algorithm based on entropic regularization.
We consider online learning in episodic loop-free Markov decision processes (MDPs), where the loss function can change arbitrarily between episodes, and the transition function is not known to the learner. We show $\tilde{O}(L|X|\sqrt{|A|T})$ regret bound, where $T$ is the number of episodes, $X$ is the state space, $A$ is the action space, and $L$ is the length of each episode. Our online algorithm is implemented using entropic regularization methodology, which allows to extend the original adversarial MDP model to handle convex performance criteria (different ways to aggregate the losses of a single episode) , as well as improve previous regret bounds.