Research map / Bandits and online learning / RL theory and MDPs
Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes
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 |
|---|---|---|---|
| Use F-EULER's Bernstein-style bonuses instead of F-UCBVI's Hoeffding-style bonuses | Factored optimistic value iteration · Episodic FMDPs | worst-case regret upper bound: \bigotilde(\sum_{i=1}^{m} \sqrt{H^2X[\idxTrans{i}] T}) -> \bigotilde(\sum_{i=1}^{m} \sqrt{HX[\idxTrans{i}]T}) | Helped |
| Use F-EULER's Bernstein-style bonuses | Factored optimistic value iteration · Episodic FMDPs | computational complexity: \bigo(mS^2AH), m times more than F-UCBVI | Hurt |
| Add an inverse-telescoping cross-component bonus to component-wise exploration bonuses | F-UCBVI · Episodic FMDPs | regret upper bound: \bigotilde(\sum_{i=1}^{m} \sqrt{D^2S_i X[\idxTrans{i}] T}) -> \bigotilde(\sum_{i=1}^{m} \sqrt{H^2X[\idxTrans{i}] T}) | Helped |
| Exploit known transition factorization with component-wise transition estimates | F-UCBVI and F-EULER · Episodic FMDPs | regret upper bound: \bigotilde(\sum_{i=1}^{m} \sqrt{HX[\idxTrans{i}]T}) | Helped |
Closest papers by meaning
- Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure (NeurIPS 2021 · similarity 0.93)
- Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting (NeurIPS 2020 · similarity 0.93)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 2024 · similarity 0.90)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.90)
- Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization (ICML 2025 · similarity 0.90)
- DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees (NeurIPS 2026 · similarity 0.89)
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.