Online Reinforcement Learning In Markov Decision Process Using Linear Programming

Abstract

We consider online reinforcement learning in episodic Markov decision process (MDP) with unknown transition function and stochastic rewards drawn from some fixed but unknown distribution. The learner aims to learn the optimal policy and minimize their regret over a finite time horizon through interacting with the environment. We devise a simple and efficient model-based algorithm that achieves \(\widetilde\{O\}(LX\sqrt\{TA\})\) regret with high probability, where \(L\) is the episode length, \(T\) is the number of episodes, and \(X\) and \(A\) are the cardinalities of the state space and the action space, respectively. The proposed algorithm, which is based on the concept of ``optimism in the face of uncertainty", maintains confidence sets of transition and reward functions and uses occupancy measures to connect the online MDP with linear programming. It achieves a tighter regret bound compared to the existing works that use a similar confidence set framework and improves computational

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keyleon2023online

Related papers

• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Efficient Learning In Non-stationary Linear Markov Decision Processes (2020)6.77
• Fast Rates For Online Learning In Linearly Solvable Markov Decision Processes (2017)0.00
• Online Sparse Reinforcement Learning (2020)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Model-based Reinforcement Learning With Multinomial Logistic Function Approximation (2022)2.26