Optimal Multi-Reward Reinforcement Learning
Abstract
We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions {r1, r2, …, 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π̂m, m where m∈ [M] represents the reward function and V0*, m=𝔼s1∼ μ[V1*, m(s1)]. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of O(SAH3/ε2log M polylog((SAHlog M)/(min{ε, 1}δ))) episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of $ \mathrm{polylog}(SAH\log M/(\min\left\{ε, 1\right\}δ))$. 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.
Related
- Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead
- Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
- Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
- Optimal Value Inference for Reinforcement Learning
- Optimal Transport Meets Reinforcement Learning: A Survey
BibTeX
@misc{chen2026optimal,
title = {{Optimal Multi-Reward Reinforcement Learning}},
author = {Zijun Chen and Zihan Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.36486},
eprint = {2609.36486},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.36486},
}
RIS
TY - UNPB
TI - Optimal Multi-Reward Reinforcement Learning
AU - Zijun Chen
AU - Zihan Zhang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.36486
UR - https://arxiv.org/abs/2609.36486
AB - We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions {r^1, r^2, …, r^M}. The goal is to output an ε-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error V_0^*, m − V_0^π̂^m, m where m∈ [M] represents the reward function and V_0^*, m=𝔼_s_1∼ μ[V_1^*, m(s_1)]. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of O(SAH^3/ε^2log M polylog((SAHlog M)/(min{ε, 1}δ))) episodes, with no additional burn-in cost. This matches the information-theoretic lower bound up to a factor of $ \mathrm{polylog}(SAH\log M/(\min\left\{ε, 1\right\}δ))$. 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.
ER -