CS Paper Radar

The Exact Boundary of Linear Optimality in Witsenhausen's Counterexample

Yikai Lu, Tongxin Li

eess.SY math.OC ·submitted 2026-10-19 06:08 UTC · v1

Abstract

Witsenhausen's counterexample has resisted a closed form solution for decades. However, it has remained unknown whether a mathematically tractable representation exists or not. In this paper, we solve this open problem, showing that the optimal policies are either linear or not tame and characterizing the exact regions where the two properties hold. Moreover, in the linear optimal region, we give an essentially unique closed form solution for the optimal policy, and show that no optimal first-stage policy is definable in any $o$-minimal expansion of the ordered real field in the nonlinear optimal region.

Comment
39 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Multistage Extension of Witsenhausen's Counterexample with Linear Signaling

eess.SY math.OC ·2026-11-08 ·Quanyan Zhu, Tamer Başar
benchmark similarity 0.64
Abstract · 8 pages, 3 figures

We study a multistage scalar extension of Witsenhausen's counterexample in which controller 1 observes the initial state exactly, whereas every subsequent controller observes only a local noise-corrupted state and does not inherit its predecessors' observations, so that every nonterminal action both regulates the state and shapes the signal available to the next controller. Restricting the signaling controllers to linear policies while leaving the terminal controller unrestricted, we compute the exact value within this class and reduce the optimization to a deterministic dynamic program in a single propagated variance. The optimal intermediate gains are shown to have a shrinkage form, and the value functions of that program are concave. For two stages, the benchmark admits a closed form on a matching locus, where for small effort weights it has two distinct minimizers, and at the standard parameter instance on that locus a two-point nonlinear policy strictly improves upon it. For three stages, numerical continuation at a reference instance reveals three distinct local minima, and two values of the initial variance at which the lowest of the three changes abruptly. Under the terminal-cost normalization we further prove, for every finite horizon, that the optimal linear value becomes asymptotically equal to the signaling-idle benchmark as the initial variance tends to infinity.

0.35

Conditions for Normality of Pontryagin's Maximum Principle in the Absence of State Constraints

eess.SY math.OC ·2026-11-03 ·André Tits, Pierre-Antoine Absil, Noé Tits
similarity 0.53
Abstract

Pontryagin's Maximum Principle is said to be "normal" for the problem at hand when it has a solution (maximizer u*) that explicitly involves the problem's cost function, making the maximum principle helpful (while in the opposite situation it is of no help). The aim of the present paper is, for Lagrange optimal control problems without state constraints, to identify classes of problems for which the Principle is normal. General conditions are introduced that guarantee normality, and classes of problems that satisfy these conditions are identified. Such classes include problems for which the constrained (by bounds on the control values) "augmented" reachable set, with cost along an upward vertical axis, has a convex lower-boundary function and the optimal terminal state lies in the relative interior of the reachable state set, with the terminal constraint within the affine hull of that set. Such classes include problems for which the constrained (by bounds on the values of the control signal) "augmented" (with the cost value along an upward "vertical axis") reachable set has a "convex" lower boundary for which the optimal terminal state lies in the relative interior of the set of reachable states. Special attention is given to Lagrange steering problems: sufficient conditions are obtained on a nested sequence of sub-classes of such problems, culminating with the class of steering problems with scalar control signal and linear time-invariant (LTI) state dynamics and objective integrand, for which normality is guaranteed whenever all eigenvalues of the state dynamics matrix A are real (e.g., if A is symmetric or triangular or the system is overdamped) or have small enough imaginary parts; simple 2 x 2 examples show that, in contrast with the situation in the finite-dimensional case, this property does not extend to arbitrary A matrices.

0.31

Infinite Horizon Mean-Field Terminal Value Problem

eess.SY math.OC ·2026-09-11 ·Uğur Aydın, Tamer Başar, Naci Saldi
similarity 0.53
Abstract · 39 pages, 2 figures

We introduce a class of finite- and infinite-horizon discrete-time control problems for studying macroscale systems in discrete time, which we refer to as mean-field terminal value problems (MFTVPs). An MFTVP takes a terminal \(Q\)-function as input and, starting from this terminal \(Q\)-function, seeks an indefinite backward evolution of optimal policies and state measures, as required for an infinite-horizon non-stationary mean-field equilibrium (MFE) of a discrete-time mean-field game (MFG). We study the existence and uniqueness properties of this problem. As an application, using the uniqueness properties of MFTVPs, we show that, in the average-cost setting (and in the discounted setting for sufficiently small discount factors), MFTVPs can be used as an intermediate step to develop approximation schemes between finite-horizon MFEs and average-cost MFEs (respectively, stationary MFEs). In contrast to approaches that use infinite-horizon MFGs as intermediate problems, MFTVPs can be employed when the discount factor is sufficiently small (or, in the average-cost setting, when the drift factor is sufficiently small), together with a regularizer, to approximate a stationary MFE. Assuming uniqueness of the solution of a MFTVP, the restrictions we impose on the Lipschitz parameters of the system are weaker than the contraction conditions available for regularized stationary MFGs, and our approximation scheme remains applicable even in the presence of multiple stationary MFEs.

0.31

Threshold Structure of Optimal Policies in Restart POMDPs

cs.LG math.OCmath.PR ·2026-08-11 ·Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang
publishedtheory similarity 0.53
Abstract · 8 pages, the paper has been accepted to IEEE CDC 2026

We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

0.25

Algorithmic Optimality Guarantees for Nonsmooth $H_\infty$ Output-Feedback Policy Search

cs.LG math.OCeess.SY ·2026-09-05 ·Ashkan Soleymani, Patrick Jaillet
publishedbenchmarktheory similarity 0.52
Abstract · Appeared at The 65th IEEE Conference on Decision and Control (CDC), 2026

We study continuous-time full-order dynamic output-feedback $H_\infty$ policy search, a nonconvex and nonsmooth problem. Direct policy search is a central paradigm in reinforcement learning and continuous control, but rigorous guarantees remain scarce in robust output-feedback settings. The $H_\infty$ problem is a canonical benchmark because it captures disturbance attenuation and robustness while exposing the hard nonsmooth geometry of policy-space optimization. We prove that on the exact identity-gauge slice of the extended convex lift, $\varepsilon$-stationarity yields $O(\varepsilon)$-suboptimality on compact exact slices, which in turn yields convergence-rate guarantees for nonsmooth policy-search methods. This result addresses the finite-time optimality-gap question raised by Guo and Hu [2022] in the more general dynamic output-feedback $H_\infty$ policy-search setting. We further use the established value equivalence supplied by extended convex lifting to formulate a nonstrict-feasibility bisection method with one final strict-feasibility recovery step, yielding an explicit $\varepsilon$-optimal stabilizing controller. These results provide a quantitative and algorithmic strengthening of prior qualitative optimality theory for nonsmooth $H_\infty$ policy search.

0.17

On the Value Function of Infinite-Horizon Optimal Control of Piecewise Affine Systems

eess.SY math.OC ·2026-08-20 ·Francesco Cordiano, Kanghui He, Bart De Schutter
similarity 0.52
Abstract · Submitted to IEEE Transactions on Automatic Control

In this paper, we study the structure of the value function in constrained infinite-time optimal control (CITOC) problems of piecewise affine (PWA) systems, with $\ell_1$ or $\ell_\infty$ stage cost. Existing works, such as [1], establish that the resulting value function is PWA in the state. However, existing results do not analyze whether the value function is a proper PWA function, i.e., with a finite number of affine pieces over compact sets, or whether the number of pieces can be infinite. We show that the latter case is indeed possible by means of an explicit example, which is also instrumental in establishing rigorous and easily verifiable sufficient conditions that ensure that the resulting value function is a proper PWA function. Our theoretical findings complement well-known results, e.g., the linear-quadratic case, and serve as support for recent learning-based control schemes for PWA systems. Throughout the paper, the proposed results are illustrated by means of a numerical example.

0.15

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.52
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

Homological Barriers to Stable Learning of First-Order Nash Equilibria

cs.GT cs.LG ·2026-11-08 ·Ashkan Soleymani, Gabriele Farina, Patrick Jaillet, Georgios Piliouras
published similarity 0.50
Abstract · The Fortieth Annual Conference on Neural Information Processing Systems (NeurIPS) 2026

We identify a homological barrier to stable learning of local Nash equilibria, also known as first-order Nash equilibria (FONE), in constrained non-concave differentiable games. We consider continuous deterministic learning dynamics that fix every FONE point and aim to attract all initial conditions to the full FONE set. We show that this convergence guarantee is impossible when the target set has nontrivial positive-degree cohomology, such as that arising from a loop, and the state space is compact and contractible. We exhibit this barrier in a simple non-concave quadratic zero-sum game on a box whose exact FONE set consists of a diagonal six-edge loop and an isolated point. Consequently, no such dynamics can make the full FONE set a stable global attractor. We further show that degree two is the minimal polynomial degree at which this barrier can arise and extend the construction to obtain nontrivial homology in arbitrarily high degrees. Finally, we establish that the barrier persists for sufficiently small approximate-FONE targets under small perturbations, yielding an open, positive-volume family of quadratic zero-sum games with the same homological barrier.

0.41