Research map / Bandits and online learning / RL theory and MDPs
Online Episodic Convex Reinforcement Learning
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.
Gives the first online CURL algorithm with sublinear regret under unknown transitions and adversarial convex losses (full-information via OMD with exploration bonuses), plus bandit-feedback variants for RL and CURL.
Problem
Online episodic finite-horizon MDPs with convex objectives on state-action distributions (concave utility RL / convex RL), with adversarial losses and unknown transition kernel, under full-information and bandit feedback.
Approach
Run online mirror descent over occupancy measures induced by the estimated kernel, adding count-based exploration bonuses to the (sub)gradient so that the policy is closed-form and explores without requiring model optimism; for bandit CURL, apply bandit convex optimization gradient estimators (entropic one-point and self-concordant log-barrier) to the MDP occupancy-measure set.
Key results
- Full-information Bonus O-MD-CURL achieves regret Õ(L N^3 |X|^{3/2} sqrt(|A| T)) without knowing transitions.
- Bandit RL variant achieves Õ(sqrt(T)) regret; bandit CURL with entropic regularization achieves Õ(T^{3/4}) under a minimum-transition-probability assumption, and self-concordant method achieves Õ(T^{3/4}) for known MDP.
- In gridworld experiments Bonus O-MD-CURL reaches targets faster than Greedy MD-CURL and succeeds in the constrained MDP where Greedy MD-CURL fails.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add exploration bonuses to the OMD update | Bonus O-MD-CURL versus Greedy MD-CURL · Multi-objectives | speed of reaching targets | Helped |
| add exploration bonuses to the OMD update | Bonus O-MD-CURL versus Greedy MD-CURL · Constrained MDP | target-state reachability while avoiding constraint states | Helped |
Surprising findings
- Greedy MD-CURL fails to reach the target in the constrained MDP even after 1000 iterations.
Limitations
- Bandit CURL with unknown MDP only has the regret bound under a minimum transition probability assumption, and the bound depends on that constant.
- Regret bounds have extra factors of N and sqrt(|X|) compared with optimal RL rates.
- Bandit CURL bounds are T^{3/4}, not the optimal sqrt(T), and the self-concordant method is restricted to known MDPs.
Experimental setup
Benchmarks: four-room gridworld multi-objective task four-room gridworld constrained MDP task
Metrics: log-loss regret
Baselines: Greedy MD-CURL
Builds on: Concave utility reinforcement learning Greedy MD-CURL dilated bonuses UCB-VI bandit convex optimization
Closest papers by meaning
- MetaCURL: Non-stationary Concave Utility Reinforcement Learning (NeurIPS 2024 · similarity 0.92)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.89)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.89)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.88)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.88)
- Online Markov Decision Processes Configuration with Continuous Decision Space (AAAI 2024 · similarity 0.88)
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.