Research map / Bandits and online learning / RL theory and MDPs
Learning Adversarial Markov Decision Processes with Delayed Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add explicit exploration, forcing uniform actions until sufficient feedback is observed (ablation) | Delayed OPPO · Unknown transition, delayed trajectory, full-information | regret upper bound: H^2 S A d_{max} -> H^2 S d_{max} | Helped |
| Skip feedback whose delay exceeds β | Delayed OPPO with explicit exploration · Unknown transition, delayed trajectory, full-information | regret upper bound: H^2 S d_{max} -> H^{3/2} \sqrt{S D} | Helped |
| Use Delayed O-REPS instead of Delayed OPPO | Delayed policy optimization methods · Known transition, delayed trajectory, full-information | regret upper bound: H^2 \sqrt{K + D} -> H \sqrt{K + D} | Helped |
| Use delayed full-information feedback with unknown transitions | Delayed OPPO · Unknown transition, delayed trajectory, full-information | regret upper bound: H^2 \sqrt{D} -> H^{3/2} \sqrt{S D} | Mixed |
| Use bandit feedback rather than full-information feedback | Delayed OPPO · Unknown transition, delayed cost, non-delayed trajectory | regret upper bound: H^{3/2} S \sqrt{A K} + H^2 \sqrt{D} -> H S \sqrt{A} K^{2/3} + H^2 D^{2/3} + H^2 d_{max} | Hurt |
| Use stochastic costs and replace importance-sampling estimators with empirical averages | Delayed OPPO · Unknown transition, delayed trajectory, bandit | regret upper bound: H S \sqrt{A} K^{2/3} + H^2 D^{2/3} -> H^2 S \sqrt{A K} + H^2 S d_{max} | Helped |
| Use a black-box reduction with parallel non-delayed algorithms | Delayed adversarial MDP learning · Delayed feedback, full-information or bandit | regret upper bound: \widetilde O ( H^2 S \sqrt{A K (d_{max}+1)} + H^2 S^2 A (d_{max}+1) ) | Hurt |
Closest papers by meaning
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.92)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.92)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.91)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.91)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.90)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · 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.