Research map / Bandits and online learning / RL theory and MDPs
Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PSConRL, a posterior-sampling algorithm for infinite-horizon average-reward communicating CMDPs that uses LP-based occupancy-measure policies and shortest-path exploration when sampled CMDPs are infeasible, achieving Bayesian regret Õ(DS√(AT)) per cost component.
Problem
Learning in infinite-horizon average-reward constrained MDPs (communicating class) with low regret and constraint violation, where existing algorithms are either suboptimal, computationally intractable, or restricted to ergodic CMDPs.
Approach
Posterior sampling over transitions per episode; when the sampled CMDP's LP is infeasible, the agent switches to shortest-path exploration toward the least-visited state, otherwise it solves the occupancy-measure LP. This yields near-optimal Bayesian regret and cost violation for communicating CMDPs with a computationally efficient algorithm.
Key results
- Proves Bayesian regret and constraint violation bound of Õ(DS√(AT)) per cost component for communicating CMDPs, matching the Ω(√(DSAT)) lower bound in T.
- On Marsrover 4x4 and 8x8, PSConRL shows lower cumulative regret than C-UCRL, UCRL-CMDP and FHA, with constraint violation comparable to C-UCRL.
- On the Box environment PSConRL significantly outperforms C-UCRL, which incurs near-linear regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PSConRL instead of the compared algorithms | Constrained RL · Marsrover 4x4, Marsrover 8x8, and Box | cumulative regret | Helped |
| Use PSConRL instead of C-UCRL | Constrained RL · Box | cumulative regret | Helped |
| Use PSConRL instead of C-UCRL | Constrained RL · Marsrover 4x4 and Marsrover 8x8 | cumulative constraint violation | No clear effect |
| Add shortest-path exploration when the sampled CMDP is infeasible, rather than ignoring constraints and using the unconstrained optimal policy | Posterior sampling for communicating CMDPs · Two-state CMDP example | average constraint cost | Helped |
| Add shortest-path exploration when the sampled CMDP is infeasible | Posterior sampling for communicating CMDPs · Two-state CMDP example | learning the true transition parameter | Helped |
Surprising findings
- PSRL-CMDP, which ignores infeasibility by dropping constraints, severely violates the constraint on a two-state toy example, showing exploration is needed for communicating CMDPs.
Limitations
- Theoretical bound is Bayesian rather than frequentist; the authors conjecture but do not prove a frequentist bound.
- Empirical baselines were adapted to unknown rewards/costs and transitions, and PSRL-CMDP and Alg. 4 were omitted from experiments.
- Gap of O(√(DS)) between upper and lower bounds remains open.
Experimental setup
Datasets: Marsrover 4x4 Marsrover 8x8 Box gridworld
Benchmarks: Marsrover 4x4 Marsrover 8x8 Box
Metrics: cumulative regret cumulative constraint violation
Baselines: C-UCRL UCRL-CMDP FHA (Alg. 3) PSRL-CMDP
Builds on: PSRL UCRL-CMDP C-UCRL Ouyang et al. occupancy-measure LP for CMDPs
Closest papers by meaning
- Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (NeurIPS 2017 · similarity 0.95)
- Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (ICML 2017 · similarity 0.92)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.91)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.91)
- Truly No-Regret Learning in Constrained MDPs (ICML 2024 · similarity 0.90)
- Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.