Research map / Bandits and online learning / RL theory and MDPs

Multi-objective Linear Reinforcement Learning with Lexicographic Rewards

ICML 2025 · Bandits and online learning › RL theory and MDPs · approach: Linear function approximation in RL

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes LLRL, a multi-stage confidence-based action elimination algorithm for linear MOMDPs with lexicographic rewards, giving the first regret bounds for multi-objective RL (including a misspecified setting).

Problem

Multi-objective RL with lexicographically ordered objectives in linear MDPs lacks theoretical regret guarantees, and Bellman optimality fails for secondary objectives, breaking greedy action selection.

Approach

Decomposes action selection into stages: lexicographic action elimination uses per-objective confidence thresholds scaled by Λ_i(λ) to keep the lexicographically optimal action, with geometrically shrinking thresholds 2^{-s} across stages, plus least-squares backward Q-updates per objective.

Key results

• Regret bound of Õ(Λ_i(λ)·√(d²H⁴K)) for every objective i in linear MOMDPs with lexicographic rewards, with Λ_i(λ)=1+λ+…+λ^{i-1}.
• Misspecified ϵ-approximate setting gives regret Õ(Λ_i(λ)·(√(d²H⁴K)+ϵdH²K)).
• For the primary objective (Λ_1=1), the bound improves on Jin et al. (2020) in dependence on d.

Surprising findings

• Bellman optimality fails for secondary lexicographic objectives, so greedy argmax-Q action selection (LSVI-UCB style) can be suboptimal.

Limitations

• Analysis relies on Assumption 1 bounding inter-objective trade-offs via λ; unclear if removable.
• Regret bound for objectives beyond the first is inflated by Λ_i(λ) and the bound is not tight in H compared with LSVI-UCB++ single-objective result.
• Computational complexity has an O(K^2) term, higher than standard bandit algorithms.

Experimental setup

Metrics: regret bound (theoretical)

Baselines: LSVI-UCB LSVI-UCB++ Zanette et al. (2020)

Builds on: LSVI-UCB LSVI-UCB++ Linear MDP regret framework (Jin et al., 2020)

Closest papers by meaning

• An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning (NeurIPS 2024 · similarity 0.90)
• On Generalization Across Environments In Multi-Objective Reinforcement Learning (ICLR 2025 · similarity 0.89)
• Preference Conditioned Multi-Objective Reinforcement Learning: Decomposed, Diversity-Driven Policy Optimization (NeurIPS 2026 · similarity 0.89)
• On the Expressivity of Objective-Specification Formalisms in Reinforcement Learning (ICLR 2024 · similarity 0.88)
• Reinforcement Learning with LTL and $\omega$-Regular Objectives via Optimality-Preserving Translation to Average Rewards (NeurIPS 2024 · similarity 0.87)
• Multi-Objective Reinforcement Learning with Max-Min Criterion: A Game-Theoretic Approach (NeurIPS 2025 · similarity 0.87)