Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models
Organizations: University of Central Florida
Abstract
In multi-objective reinforcement learning, preferences may be specified only after data collection, requiring one dataset to support a continuum of reward trade-offs. We study finite discounted Markov decision processes with unknown transitions, states, actions, and known reward functions taking values in , given access to a generative model. The learner must provide an -optimal policy for every convex combination of these rewards without further sampling, with a guarantee that holds simultaneously over all preferences and initial states. Writing , we establish the constant-confidence minimax sample complexity , where the suppressed factors are logarithmic in and the dependence on is explicit. Thus, up to these logarithmic factors, the worst-case statistical cost of supporting all preferences grows logarithmically with the number of objectives and saturates at the number of states. The upper bound uses uniform state--action sampling and empirical planning, with reward rounding in the logarithmic-objective regime. Its analysis chains optimal-value increments over covers of the reward hull. A one-sided Bellman variance bound controls signed value differences under a second transition kernel, preserving the dependence. A complementary uniform guarantee for all bounded rewards yields the state-dimension saturation. We establish lower bounds matching up to logarithmic factors through a rare-exit construction with subset rewards and action encoding. These bounds apply to adaptive simulator queries and arbitrary randomized history-dependent output policies, while the upper bounds are attained by deterministic stationary policies.
Figures & tables
| Work | Access | Rewards served | Upper bound | Lower bound |
|---|---|---|---|---|
| Zhou et al. [ 8 ] | generative, discounted | -values for all with | single objective only | |
| Net + planning [ 6 , 7 ] | generative, discounted | – | ||
| Wu et al. [ 17 ] | online, episodic | , preferences revealed later | † | |
| Jin et al. [ 20 ] | online, episodic | all rewards, revealed later | ||
| Zhang et al. [ 21 ] | online, episodic | tasks, unknown during exploration | ||
| Li et al. [ 23 ] | online, episodic | given rewards; all rewards | ‡ ; | – |
| Learning target | Reward information during sampling | Query class |
|---|---|---|
| Fixed reward | One scalar reward is known | The singleton |
| Finite known tasks | The rewards are known | The finite set |
| Uniform MORL (this work) | The rewards are known; the query preference is not | The reward hull |
| Reward-free learning | No reward is known | Every reward in |
Multi-Objective Reinforcement Learning
Multi-objective reinforcement learning studies how agents can balance competing goals and learn policies for different trade-offs.
See all 159 papers