Research map / Reinforcement learning / MDPs and planning
Beyond Scalar Rewards: An Axiomatic Framework for Lexicographic MDPs
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.
Extends Hausner's lexicographic expected utility to sequential decision-making, showing that a safety-first axiom forces 2-dimensional lexicographic rewards in MDPs and that optimal policies in these lexicographic MDPs keep scalar-MDP properties unlike CMDPs.
Problem
When scalar rewards can represent an agent's preferences in sequential decision-making, and what structure lexicographic (non-continuous) preferences impose on rewards and optimal policies in MDPs.
Approach
Introduces a Safety First axiom with an infinitely bad outcome that violates continuity, under which preferences need a 2-dimensional lexicographic utility; combined with memorylessness this yields recursive lexicographic returns (LMDPs) with transition-dependent matrix reward multipliers, and proves a fundamental theorem of LMDPs guaranteeing stationary uniformly optimal policies.
Key results
- Under the Safety First axiom, preferences are representable by a 2-dimensional linear lexicographic utility u(o)=(0,u'(o)) for safe outcomes and (-1,0) for the unsafe outcome, unique up to lower-triangular affine maps.
- Under memorylessness, the sequential utility satisfies u(e·τ)=r(e)+Γ(e)u(τ) with Γ in lower-triangular matrices; with diagonal entries below 1, a stationary deterministic uniformly optimal policy exists for every finite LMDP.
- In contrast to CMDPs, where optimal policies may need to randomize and uniformly optimal stationary policies may not exist, LMDPs violate only continuity (not independence), so scalar-MDP optimality properties carry over.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Adding a safety-first axiom (infinitely bad outcome o†) that violates Continuity, yielding a 2-dimensional lexicographic utility instead of a scalar | MDP preferences over outcomes · theoretical (axiomatic) | dimensionality of utility representation | No clear effect |
| Assuming diagonal entries of reward multipliers Γ(e) are below 1 (fundamental theorem of LMDPs) | lexicographic MDPs · theoretical (finite LMDPs) | existence of stationary deterministic uniformly optimal policy | Helped |
| Using a CMDP (constrained) formulation instead of lexicographic/MDP objective | constrained MDPs · theoretical comparison | existence of uniformly optimal stationary policy | Hurt |
Surprising findings
- Optimal policies in CMDPs may need to randomize and may not admit a uniformly optimal stationary policy, whereas LMDPs keep this property.
Limitations
- Lexicographic objectives are only appropriate when objectives cannot be traded off, which may be uncommon in practice.
- No new algorithms are proposed for solving lexicographic MDPs.
- Analysis focuses on environment-independent reward specification; known environments may admit simpler scalar rewards.
Experimental setup
Baselines: Constrained MDP penalty method (scalarization)
Builds on: von Neumann-Morgenstern expected utility theorem Hausner lexicographic expected utility Constrained MDP
Closest papers by meaning
- Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback (ICML 2025 · similarity 0.87)
- Multidimensional Bayesian Utility Maximization: Tight Approximations to Welfare (NeurIPS 2025 · similarity 0.86)
- Omega-Regular Decision Processes (AAAI 2024 · similarity 0.86)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
- An Analytical Study of Utility Functions in Multi-Objective Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.