Research map / Reinforcement learning / MDPs and planning
Optimizing Local Satisfaction of Long-Run Average Objectives in Markov Decision Processes
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.
Formalizes local satisfaction of long-run average objectives in MDPs, proves NP-hardness, and proposes LocalEval (evaluation) and LocalSynt (gradient-descent strategy synthesis optimizing global satisfaction, renewal-time stability and determinism).
Problem
Long-run average objectives in MDPs constrain steady-state state frequencies, but optimal policies may be locally unstable: frequencies over bounded time horizons deviate from the limit frequency, so the objective is often not met locally.
Approach
Define local badness as the expected badness of frequencies over a window of n states sampled from the invariant distribution, and synthesize finite-memory randomized strategies by jointly minimizing a differentiable combination of global objective, renewal-time variance (stability) and renewal-time variance per vertex (determinism), optimized by gradient descent.
Key results
- LocalSynt-constructed strategies for D_n outperform hand-crafted strategies pi_n and rho_n for all n>=4 in local badness (e.g., n=6: 0.080 vs 0.175 and 0.140).
- LocalSynt handles instances with thousands of parameters (n=20, 2725 parameters, ~0.2 s per step), whereas LocalEval times out for d around 30 and the naive DFS algorithm times out already at n=6.
- Theorem: computing a finite-memory strategy with zero local badness for a given horizon is NP-hard even for graphs (reduction from Hamiltonian cycle).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LocalSynt instead of the hand-designed π and ϱ strategies | D4–D8 · D4–D8 | L-badness: D4: 0.17131 -> 0.10540; D5: 0.11762 -> 0.10540; D6: 0.13985 -> 0.08016; D7: 0.10456 -> 0.10022; D8: 0.11436 -> 0.10012 | Helped |
| Increase memory allocated to vertex R (ablation) | LocalSynt on the Fig. 1 graph · Fig. 1 graph | L-badness | Helped |
| Set β and γ to zero, removing both stability/determinism penalties (ablation) | LocalSynt · Fig. 1 graph | L-badness | Hurt |
| Increase β + γ to 0.5 or higher (ablation) | LocalSynt · Fig. 1 graph | L-badness | Hurt |
| Use β = 0.0 and γ = 0.2 (ablation) | LocalSynt · Dn, n=2–8 | L-badness | Helped |
| Optimize local satisfaction rather than requiring the invariant distribution to equal ν | LocalSynt σ6 · D6 | L-badness: 0.13985 -> 0.08016 | Helped |
| Use LocalSynt rather than the DFS-based naive evaluator | D5 · D5 | evaluation runtime (seconds): 1.21E+02 -> 4.56E-03 | Helped |
Surprising findings
- The best synthesized strategies often have an invariant distribution different from the desired one, trading global satisfaction for local satisfaction.
- Setting beta=gamma=0 (ignoring stability and determinism terms) or beta+gamma around 0.5 or higher produces poor strategies.
Limitations
- Experiments are restricted to graphs (no stochastic vertices) to separate strategy randomness from MDP randomness.
- LocalEval does not scale to large horizons, so local badness of synthesized strategies for large n cannot be verified.
- Problem is NP-hard and PSPACE-hard for general MDPs with stochastic vertices, so the method is heuristic.
Experimental setup
Benchmarks: graph of Fig. 1(a) with varying time horizon d parameterized graph family D_n for n=2..8 and scalability up to n=20
Metrics: L-Badness (local badness) running time in seconds
Baselines: naive DFS-based evaluation hand-crafted strategies pi_n and rho_n
Builds on: Steady-state strategy synthesis (Brázdil et al. 2011) Expected window mean-payoff (Bordais et al. 2019) Velasquez 2019 / Atia et al. 2020 memoryless steady-state synthesis Adam optimizer PyTorch automatic differentiation
Closest papers by meaning
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.86)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.86)
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.86)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
- On the Convergence of Success Conditioning for Policy Optimization (NeurIPS 2026 · similarity 0.85)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 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.