Research map / Learning theory and algorithms / Submodular and game algorithms
Multiple Mean-Payoff Optimization Under Local Stability Constraints
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 a differentiable dynamic-programming strategy synthesis method that optimizes multiple window mean payoffs (local stability) over finite-memory randomized strategies in MDPs, trading optimality for scalability.
Problem
Synthesizing controllers in MDPs that simultaneously optimize multiple mean payoffs while enforcing local stability via window mean payoffs; the exact problem is NP-hard and no scalable algorithm existed.
Approach
Computes the expected value of a decomposable evaluation function over window mean payoffs via a dynamic programming procedure over representatives (differentiable), enabling gradient-based strategy improvement with random-restart gradient descent over finite-memory randomized strategies (WINMPSYNT).
Key results
- Best strategies found reach wval bound 0 (optimal) in 40% of scenarios and within 0.1 of optimum in 100% of scenarios.
- Dynamic programming evaluation runs under one second for the (30,30) scenario, while DFS times out at 20 s for l=d<=20 with one memory state.
- Increasing memory states lowers average strategy value, and randomization compensates for insufficient memory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the dynamic-programming evaluation procedure instead of the DFS-based procedure | WINMPSYNT · Dℓ instances with ℓ=d, 4≤ℓ≤30 | training-step time: less than one second; DFS reaches the 20 secs timeout for ℓ=d≤20 | Helped |
| increase the number of memory states assigned to each vertex | WINMPSYNT · Dℓ scenarios grouped by optimal memory requirement Kℓ,d | average strategy value (wval) | Helped |
| use randomized strategies when memory is below the amount required by an optimal strategy | WINMPSYNT · Dℓ scenarios | strategy value (wval) | Helped |
| select the best of 500 constructed strategies for each scenario | WINMPSYNT · Dℓ scenarios | best strategy wval: 40% of scenarios ≤ 0; 52% ≤ 0.05; 100% ≤ 0.1 | Helped |
| evaluate the full set of constructed strategies rather than selecting the best per scenario | WINMPSYNT · All Dℓ scenarios and memory sizes | strategy value (wval): 6% ≤ 0; 27% ≤ 0.1; 99.8% ≤ 0.3 | Mixed |
Surprising findings
- Randomized strategies with K memory states can strictly beat the best deterministic strategies with the same K memory states (Example 1).
Limitations
- Computed solutions are not guaranteed to be optimal; NP-hardness implies no efficient exact algorithm.
- Experiments only on structured ring graphs rather than general MDPs.
- Average strategies are substantially worse than best-of-100 strategies.
Experimental setup
Benchmarks: parameterized ring graphs D_l with window length d scenarios (l,d in [2,20])
Metrics: normalized Eval value (wval) average training step time fraction of scenarios reaching optimal bound
Baselines: DFS-based evaluation procedure
Builds on: window mean payoff (Chatterjee et al. 2015) multiple mean-payoff MDP optimization (Brázdil et al. 2011) PyTorch automatic differentiation with Adam
Closest papers by meaning
- Optimizing Local Satisfaction of Long-Run Average Objectives in Markov Decision Processes (AAAI 2024 · similarity 0.84)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.82)
- Boosting Perturbed Gradient Ascent for Last-Iterate Convergence in Games (ICLR 2025 · similarity 0.82)
- Contextual Linear Bandits with Delay as Payoff (ICML 2025 · similarity 0.82)
- Finite-Sample Convergence Bounds for Trust Region Policy Optimization in Mean Field Games (ICML 2025 · similarity 0.82)
- Anytime-Constrained Equilibria in Polynomial Time (ICML 2025 · similarity 0.82)
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.