stat.MLNov 3, 2026

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models

Authors: Yue Wang

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, SS states, AA actions, and mm known reward functions taking values in [0,1][0,1], given access to a generative model. The learner must provide an ε\varepsilon-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 H=(1−γ)−1H=(1-γ)^{-1}, we establish the constant-confidence minimax sample complexity Θ~ ⁣(SAH3ε2min⁡{S,log⁡(em)})\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right), where the suppressed factors are logarithmic in S,A,H,ε−1S,A,H,\varepsilon^{-1} and the dependence on mm 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 H3ε−2H^3\varepsilon^{-2} 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

Explore similar work

CardsList
  1. Optimal Multi-Reward Reinforcement Learning

    Sep 29, 2026Zijun Chen, Zihan ZhangMarkov Decision ProcessesSample-Efficient RL

  2. Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RL

    Nov 14, 2026Matthew Zurek, Yudong ChenReinforcement LearningSample-Efficient RL

  3. Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

    Oct 3, 2026Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh TalebiRisk-Sensitive RLSample-Efficient RL