mlsanityData to 14 Oct 2026

Optimal Multi-Reward Reinforcement Learning

arXiv 2609.36486 ↗First posted 29 Sep 2026cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions r1, r2, ldots, rM. The goal is to output an ε-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error V0*, m - V0^widehatπm, m where m∈ [M] represents the reward function and V0*, m=mathbbEs1~ μ[V1*, m(s1)]. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of Oleft(fracSAH3ε2log M polylogleft(fracSAHlog Mminleftε, 1rightδright)right) episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of polylog(SAHlog M/(minleftε, 1rightδ)). Our method combines three technical ingredients. First, we adapt MVP to reward-switching learning to construct optimistic value estimates. Second, we use fresh replay samples to conservatively evaluate the candidate policies. Third, gap-based multiplicative weights updates adjust the reward-sampling distribution using the differences between these estimates, converting weighted learning progress into simultaneous guarantees for all rewards.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 26 of its 29 references that are in the map. First posted on arXiv 29 Sep 2026.

Builds on

26 of 29 references.

References · 26

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2015Contextual Markov Decision Processescited by 220
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  5. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  8. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  9. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  10. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  11. 2020Q-learning with Logarithmic Regretcited by 60
  12. 2019Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDPcited by 55
14 more
  1. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  2. 2020A Unifying View of Optimism in Episodic Reinforcement Learningcited by 52
  3. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 49
  4. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  5. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  6. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  7. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  8. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 35
  9. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  10. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 18
  11. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  12. 2022Near-Optimal Regret Bounds for Multi-batch Reinforcement Learningcited by 13
  13. 2025Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPscited by 4
  14. 2026Improved Bounds for Reward-Agnostic and Reward-Free Explorationcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnable
  2. 2021Reinforcement Learning in Reward-Mixing MDPs
  3. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning
  4. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
  5. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  6. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  7. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes
  8. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochs