Metraipolis › archive › dc_a32e017e3909

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05562
License (as archived)
CC0-1.0
Archived
2026-11-05T18:22:32.232Z
SHA-256 of the archived text
64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97
Stable URL of this page
https://metraipolis.com/documento/dc_a32e017e3909

How to cite

Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562 — arXiv (en), https://arxiv.org/abs/2611.05562 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a32e017e3909 (Metraipolis archive dc_a32e017e3909, sha256 64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97)
BibTeX
@misc{dca32e017e3909,
  title = {Near-Minimax Sample Complexity for Multi-Objective Reinforcement Learning under Generative Models — arXiv:2611.05562},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05562},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a32e017e3909; sha256 64e0c86a8219226f0a6d2cda2dbd1e0a8dddfe5d8dd806d6bb9dd3d06d9e1f97},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05562. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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-\gamma)^{-1}$, we establish the constant-confidence minimax sample complexity $\widetilde\Theta\!\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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.05562 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:49.030Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).