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 $\{r^1,r^2,\dots ,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^{\ast ,m}-V_0^{{\hat{\pi }}^m,m}$ where $m\in [M]$ represents the reward function and $V_0^{\ast ,m}={\mathbb{E}}_{s_1\sim \mu }[V_1^{\ast ,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}{{\epsilon }^2}\log M\mathrm{polylog}\left(\frac{SAH\log M}{\min \left\{\epsilon ,1\right\}\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 \left\{\epsilon ,1\right\}\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.