Efficient learning for multiple rewards in unknown environments
Optimal Multi-Reward Reinforcement Learning
Machine Learning
Summary
This paper looks at how to teach a computer program to make good decisions when it faces several different goals, but without knowing exactly how the world changes with its actions. The authors study a setting where the program tries many times and learns by trying, aiming to do well for all the goals. They create a new method that learns quickly and ensures good decisions for every goal with fewer trials. Their method smartly balances exploring different strategies and checking which one works best for each goal.
What this means in practice
- •For robotics engineers: Train robots to efficiently learn several tasks without resetting or separate training for each task in unknown environments.
- •For game ai developers: Develop AI agents that can quickly adapt to different game objectives during play using limited trial-and-error interactions.
Authors
Zijun Chen, Zihan Zhang
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 $ε$-optimal policy for every reward using online episodic interaction only. Performance is measured by the policy error $V_{0}^{*, m} - V_{0}^{\widehatπ^{m}, m}$ where $m\in [M]$ represents the reward function and $V_{0}^{*, m}=\mathbb{E}_{s_1\sim μ}[V_{1}^{*, m}(s_1)]$. Under this setting, we design a provably efficient algorithm to establish a minimax sample complexity bound of $$ O\left(\frac{SAH^3}{ε^2}\log M \mathrm{polylog}\left(\frac{SAH\log M}{\min\left\{ε, 1\right\}δ}\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\{ε, 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.