Reinforcement Learning Algorithms For Regret Minimization In Structured Markov Decision Processes

Abstract

A recent goal in the Reinforcement Learning (RL) framework is to choose a sequence of actions or a policy to maximize the reward collected or minimize the regret incurred in a finite time horizon. For several RL problems in operation research and optimal control, the optimal policy of the underlying Markov Decision Process (MDP) is characterized by a known structure. The current state of the art algorithms do not utilize this known structure of the optimal policy while minimizing regret. In this work, we develop new RL algorithms that exploit the structure of the optimal policy to minimize regret. Numerical experiments on MDPs with structured optimal policies show that our algorithms have better performance, are easy to implement, have a smaller run-time and require less number of random number generations.

Stats

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

Related papers

• Regret Analysis In Deterministic Reinforcement Learning (2021)0.00
• Logarithmic Regret Of Exploration In Average Reward Markov Decision Processes (2025)0.00
• Online Reinforcement Learning In Markov Decision Process Using Linear Programming (2023)3.58
• Nearly Minimax Optimal Reinforcement Learning For Linear Markov Decision Processes (2022)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Regret-optimal Model-free Reinforcement Learning For Discounted Mdps With Short Burn-in Time (2023)0.00
• Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, And Separation Design (2022)3.58
• Sharper Model-free Reinforcement Learning For Average-reward Markov Decision Processes (2023)0.00