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

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, $S$ states, $A$ actions, and $m$ known reward functions taking values in $[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-γ)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetildeΘ\!\left( \frac{SAH^3}{\varepsilon^2}\min\{S,\log(em)\} \right)$, where the suppressed factors are logarithmic in $S,A,H,\varepsilon^{-1}$ and the dependence on $m$ 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 $H^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.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 3 November 2026

  Nonparametric GARCH: An Iterated Neural Estimator

  Ruizhi Deng, Guohao Shen and Ngai Hang Chan
• arXiv preprint · 4 November 2026

  Discovering like a scientist: Literature-informed dimensionless learning for physical closure of data-driven equations

  Hao Xu, Tianhao Wu and Dongxiao Zhang
• arXiv preprint · 3 November 2026

  Descending Everest, Part II: Oracle Complexity of Minimizing a Sum of Convex $(L_0,L_1)$-Smooth Functions

  Mikhail Rudomanov, Ivan Fomin, Alexander V. Gasnikov and 1 other
• arXiv preprint · 4 November 2026

  Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities

  Huanjian Zhou and Taiji Suzuki
• arXiv preprint · 3 November 2026

  Statistical Machine Learning for Medicinal Plant Leaves Classification

  Jayani P. Gamage and Thiyanga S. Talagala

All new papers in Machine Learning (Statistics)