Optimal Multi-Reward Reinforcement Learning

We study an unknown-transition finite-horizon Markov decision process (MDP) with a finite collection of known reward functions $\{r^1,r^2,\dots ,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^{\text{*},m}-V\_0^{{\hat{\pi }}^m,m}$ where $m\in [M]$ represents the reward function and $V\_0^{\text{*},m}=\mathbb{E}\_s\_1\sim \mu [V\_1^{\text{*},m}(s_1)]$. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of $O\left(\frac{SA{H}^3}{{ϵ}^2}\log M\mathrm{polylog}\left(\frac{SAH\log M}{\min \{ϵ,1\}\delta }\right)\right)$ 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 \{ϵ,1\}\delta ))$. 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.