Research map / Bandits and online learning / RL theory and MDPs
Online Markov Decision Processes Configuration with Continuous Decision Space
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.
Studies online configuration of episodic MDPs where a configurator picks transition functions from a continuous set to minimize losses against a fixed-policy agent, proposing O-DOSC (constant regret, deterministic) and O-SOSC (sublinear regret, stochastic).
Problem
Online configuration of episodic MDPs when the configurator chooses transition functions from a continuous decision space to minimize losses (possibly unrelated to the agent's rewards) against an agent with a fixed unknown policy.
Approach
Uses occupancy measures to optimistically search the continuous space of transition functions jointly with the agent's deterministic policy, exploiting that the loss is linear in occupancy measures; deterministic losses yield constant regret, stochastic losses yield UCB-style sublinear regret.
Key results
- O-DOSC achieves regret upper bound (H+1)|X| (constant in T) in deterministic settings and a matching lower bound Omega(H|X|), and dramatically outperforms UCB1 in synthetic experiments.
- O-SOSC achieves regret eO(|X| sqrt(T) + H|X|) in stochastic settings, matching the Omega(sqrt(|X|T)) lower bound in T, and outperforms UCB1 empirically.
- Lipschitz continuity of the objective in TV distance gives a Zooming-algorithm regret of T^((1+p)/(2+p)) for p continuous parameters, which the proposed methods improve upon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use O-DOSC instead of UCB1 | Synthetic deterministic settings with discrete and continuous decision spaces · Synthetic experiments | cumulative regret | Helped |
| Use O-SOSC instead of UCB1 | Synthetic stochastic settings with discrete and continuous decision spaces · Synthetic experiments | cumulative regret | Helped |
Limitations
- Assumes the agent's policy is fixed (no dynamic or learning agent).
- Stochastic setting only achieves sqrt(T) regret with a bound that depends on |X| linearly; empirical results on continuous space are limited to synthetic MDPs.
- Requires solving an optimization over occupancy measures and policies at every episode, with computational complexity deferred to the appendix.
Experimental setup
Benchmarks: synthetic loop-free MDP (4 layers, discrete and continuous decision spaces)
Metrics: average cumulative regret
Baselines: UCB1 Zooming
Builds on: Conf-MDPs (Metelli et al. 2018) occupancy measure framework (Rosenberg and Mansour 2019) Zooming algorithm (Kleinberg et al. 2008) UCB1
Closest papers by meaning
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.89)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.89)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.89)
- Offline-Online Reinforcement Learning for Linear Mixture MDPs (NeurIPS 2026 · similarity 0.89)
- Online MDP with Prototypes Information: A Robust Adaptive Approach (AAAI 2025 · similarity 0.88)
- Achieving Constant Regret in Linear Markov Decision Processes (NeurIPS 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.