Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
We present a new algorithm based on posterior sampling for learning in Constrained Markov Decision Processes (CMDP) in the infinite-horizon undiscounted setting. The algorithm achieves near-optimal regret bounds while being advantageous empirically compared to the existing algorithms. Our main theoretical result is a Bayesian regret bound for each cost component of $\tilde{O} (DS\sqrt{AT})$ for any communicating CMDP with $S$ states, $A$ actions, and diameter $D$. This regret bound matches the lower bound in order of time horizon $T$ and is the best-known regret bound for communicating CMDPs achieved by a computationally tractable algorithm. Empirical results show that our posterior sampling algorithm outperforms the existing algorithms for constrained reinforcement learning.
Code (1)
Tasks
Efficient ExplorationSimilar Papers 제목 키워드 기반
Constrained Reinforcement Learning with Average Reward Objective: Model-Based and Model-Free Algorithms
Reinforcement Learning (RL) serves as a versatile framework for sequential decision-making, finding applications across diverse domains such as robotics, autonomous driving, recommendation systems, supply chain optimizat…
Autonomous DrivingDecision MakingmodelRecommendation Systems+2OGER: A Robust Offline-Guided Exploration Reward for Hybrid Reinforcement Learning
Recent advancements in Reinforcement Learning with Verifiable Rewards (RLVR) have significantly improved Large Language Model (LLM) reasoning, yet models often struggle to explore novel trajectories beyond their initial …
Reinforcement LearningMathematical ReasoningDistributional Reinforcement Learning for Efficient Exploration
In distributional reinforcement learning (RL), the estimated distribution of value function models both the parametric and intrinsic uncertainties. We propose a novel and efficient exploration method for deep RL that has…
Atari GamesDistributional Reinforcement LearningEfficient Explorationreinforcement-learning+2Adaptive trajectory-constrained exploration strategy for deep reinforcement learning
Deep reinforcement learning (DRL) faces significant challenges in addressing the hard-exploration problems in tasks with sparse or deceptive rewards and large state spaces. These challenges severely limit the practical a…
Deep Reinforcement LearningMuJoCoMulti-agent Reinforcement Learningreinforcement-learning+1Cost-Sensitive Exploration in Bayesian Reinforcement Learning
In this paper, we consider Bayesian reinforcement learning (BRL) where actions incur costs in addition to rewards, and thus exploration has to be constrained in terms of the expected total cost while learning to maximize…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)