Optimal Multi-Reward Reinforcement Learning

arXiv:2609.36486v1 Announce Type: new Abstract: We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions {r^1, r^2, ldots, r^M}. The goal is to output an epsilon-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error V_{0}^{, m} - V_{0}^{widehatpi^{m}, m} where min [M] represents the reward function and V_{0}^{, m}=E_{s_1sim mu}[V_{1}^{*, m}(s_1)]. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of $ Oleft(frac{SAH^3}{epsilon^2}log M polylogleft(frac{SAHlog M}{minleft{epsilon, 1right}elta}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{epsilon, 1right}elta))$. 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

• Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
• A Reward-Free Viewpoint on Multi-Objective Reinforcement Learning

Source: arXiv cs.LG | 2026-09-30