Online Convex Optimization In Adversarial Markov Decision Processes

Abstract

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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyrosenberg2019online

Related papers

• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Online Markov Decision Processes With Aggregate Bandit Feedback (2021)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Online Learning In Mdps With Partially Adversarial Transitions And Losses (2026)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Fast Rates For Online Learning In Linearly Solvable Markov Decision Processes (2017)0.00
• Online Learning In Unknown Markov Games (2020)0.00