CS Paper Radar

Attaining Optimal Values under Sure Constraints

Takuto Yamauchi, Kenji Tei

cs.GT cs.LO ·submitted 2026-11-06 10:06 UTC · v1

Abstract

A game may have, for each target below its value, a finite controller meeting that target, yet no finite controller attaining the value itself. We study finite stochastic games with a hard specification that must hold on every supported execution, including paths of probability zero. Max uses a pure finite controller; Min may use any pure public-history strategy. We distinguish three numerical questions: can a supplied target be met, can the unspecified optimum be attained, and what is one exact value? For explicit hard and Boolean soft Streett conditions, the strict and non-strict supplied-threshold problems are coNP-complete, attainment of the unsupplied supremum is $\mathrm P^{\mathrm{NP}}$-complete, and one exact reduced fraction is $\mathrm{FP}^{\mathrm{NP}}$-complete under polynomial metric reductions. The proofs preserve both the value and its finite attainability when fixing a single opponent, and encode adaptive queries without computing unknown subgame values. The same construction yields matching value-comparison and exact-output lower bounds for ordinary stochastic Streett games with unrestricted randomized history strategies. We also bound the memory needed for optimal finite implementations for arbitrary Muller hard conditions and rational rewards in $[0,1]$ determined by infinitely recurring states. One controller is sure from the entire original sure region and attains at every finitely attained start, with no attainment premise on the other states. For $n$ states in that region it uses $2^{O(n\log(n+1))}Q(1+\log R)$ modes, where $Q$ is the product of the least common denominators of full original chance rows sourced in that sure region and $R$ clears all reward values. Its joint dependence on $Q$ and $R$ is worst-case sharp at each fixed $n\ge6$ when $Q,R\ge2$. Optimal dependence on arena size and efficient general synthesis are not resolved here.

Comment
61 pages, 6 figures. Complete proofs included. Corresponding author: Takuto Yamauchi

Closest papers

Nearest neighbours by meaning across the whole index.

Subprocess-Constrained Markov Decision Processes

cs.AI ·2026-11-16 ·Jiarui Gan, Debmalya Mandal
top venuecode/data similarity 0.65
Abstract · To appear at NeurIPS '26. Code available at https://github.com/jrgan/VSI

Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce \emph{subprocess-constrained MDPs} (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within $ε$ of the optimal feasible value, it violates each subprocess cost bound by at most $δ$, and its action distribution can be computed in polynomial time for any given history.

0.47

The Stochastic Target Discounted-Sum Problem

cs.LO cs.FL ·2026-09-03 ·Nathalie Bertrand, Pranav Ghorpade, Senthil Rajasekaran, Sasha Rubin, Moshe Y. Vardi
similarity 0.64
Abstract

The target discounted-sum problem (TDS) asks, given a finite integer alphabet $Σ$, a rational discount factor $λ$, and a rational target $t$, whether some infinite sequence over $Σ$ has discounted sum exactly $t$. This problem remains open and underlies several open questions in automata theory, games, and Markov decision processes. We introduce and solve its stochastic counterpart, the stochastic target discounted-sum problem, which replaces existence by computation of the probability. We show that the probability that a random sequence generated by a finite Markov chain has discounted sum $t$ is rational and computable in pseudo-polynomial time. We further show how to decide, in polynomial time, whether the discounted-sum distribution of a Markov chain is atomless, and how to approximate to an arbitrary precision the probability that the discounted sum exceeds a rational threshold. Our techniques for the stochastic TDS problem allow us to make progress on TDS objectives in stochastic games, which are known to be as hard as the TDS problem. Restricting the maximizing player to finite-memory strategies, while allowing the minimizing player to use arbitrary strategies, we reduce the value problem and the synthesis problem to corresponding problems for safety objectives in stochastic games. This yields computable optimal values and deterministic optimal strategies with pseudo-polynomially bounded memory for stochastic games, and results in pseudo-polynomial-time algorithms for special cases of Markov decision processes and deterministic two-player games.

0.24

Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games

cs.GT cs.DS ·2026-10-09 ·Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
similarity 0.64
Abstract

Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min Player. The respective player chooses outgoing edges from their vertices. We consider these games with the classical discounted-sum and mean-payoff objectives. The goal of the Max Player is to maximize the objective against the adversarial Min Player. These games lie in NP $\cap$ coNP and are among the rare combinatorial problems that belong to this complexity class, yet the existence of a polynomial-time algorithm is a major open question. All known deterministic algorithms require exponential time in the worst case, while the classical strategy iteration (policy iteration) algorithm is remarkably efficient in practice, which motivates the study of the smoothed complexity of these games. Previous results established a smoothed polynomial-time bound only for the restricted class of ergodic games and presented only a high-probability guarantee. Our main result is a new analysis technique for a variant of the strategy iteration algorithm, and we show these algorithms achieve smoothed polynomial complexity for general game graphs with both high-probability and expected runtime guarantees. In particular, our result removes the ergodicity restriction of prior work and strengthens the high-probability guarantee to the stronger expected-runtime guarantee, thereby resolving the open question on the smoothed complexity of these games.

0.50

Sharper bounds on the thresholds for sensitive and Blackwell optimality

cs.GT ·2026-10-07 ·Xavier Allamigeon, Stéphane Gaubert, Julien Grand-Clément, Ricardo Katz
similarity 0.63
Abstract

In perfect-information two-player stochastic games, the notions of Blackwell and sensitive optimality provide generalizations of the classical mean-payoff optimality and discount optimality criteria to account for more farsighted preferences. We provide bounds on the Blackwell threshold $α_{\sf bw}$ and the $d$-sensitive thresholds $α_{\sf d}$, defined as the smallest discount factors above which discount optimal policies coincide with Blackwell optimal policies and $d$-sensitive optimal policies respectively. Our refined bounds improve upon prior work by focusing on ``reduced'' families of polynomials and, crucially, our bounds are tight in terms of controlling the degrees and heights of the minimal polynomials of the Blackwell thresholds. We apply classical root separation based on Mahler's and Cauchy's bounds to our reduced families to derive the strongest upper and lower bounds on $α_{\sf bw}$ in the literature, and we are the first to obtain bounds on $α_{\sf d}$ in the multichain stochastic setting.

0.30

Polynomial-Time Computation of Extensive-Form Proper Equilibria in Two-Player Zero-Sum Games

cs.GT cs.AIcs.MAecon.TH ·2026-11-04 ·Sam Ganzfried
similarity 0.63
Abstract

We give a deterministic polynomial-time algorithm for computing an exact extensive-form proper equilibrium in a finite two-player zero-sum extensive-form game with perfect recall and rational data. Properness is understood in the agent normal form: an action at an information set is penalized relative to a better action while all other local behavioral choices, including the player's own future actions, remain fixed. Our algorithm assigns each information set a geometric permutahedron of allowable action probabilities. A scaled doubly stochastic representation embeds these restrictions in a polynomial-size sequence-form polytope; a saddle point then satisfies the local $\varepsilon$-properness inequalities. To obtain an exact equilibrium rather than a solution at an arbitrarily small numerical perturbation, we establish sign stability of a parametric linear system, construct a persistent feasible basis, and extract the limits of behavioral ratios. The resulting probabilities are rational and have polynomial encoding length, including at information sets whose realization probabilities vanish.

0.25

Epsilon-Nash Equilibria in History-Dependent SA-MDPs

cs.GT cs.CR ·2026-09-16 ·Brandon Gary Kaplowitz, Dominik Bohnet Zurcher, Akash Agrawal, Tala Jafari, Christian Schroeder de Witt +1 more
theory similarity 0.62
Abstract

We study state-adversarial Markov decision processes (SA-MDPs) as games of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. History dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. Our main result presents the first algorithmic route to computing $ε$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We test our algorithm on small analytically verifiable games and show that it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.

0.21

Linear Bandits under Exact Sliding-Window Constraints

cs.LG ·2026-10-06 ·Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar Vakili
similarity 0.62
Abstract · 53 pages, including supplementary material; 8 figures and 6 tables

We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when $w\mid T$ and within an additive $O(w)$ gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter $D$ that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of $\widetilde{O}(d\sqrt{T}+dD+w)$. We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.

0.23

Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

cs.GT cs.LGstat.ML ·2026-09-17 ·Lishang Xu, Guodong Ma, Pengcheng Weng, Zixuan Xia
similarity 0.62
Abstract · v3: exposition clarified; a sentence in Section 5.3 that was inaccurate for K > N removed, and the K = N condition stated in the introductio…

Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(θ)\mathcal{X}(θ)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.

0.19