Irmak Sağlam

AAAI Conference 2026 Conference Paper

Incremental Data-Driven Policy Synthesis via Game Abstractions

• Irmak Sağlam
• Mahdi Nazeri
• Alessandro Abate
• Sadegh Soudjani
• Anne-Kathrin Schmuck

We address the synthesis of control policies for unknown discrete-time stochastic dynamical systems to satisfy temporal logic objectives. We present a data-driven, abstraction-based control framework that integrates online learning with novel incremental game-solving. Under appropriate continuity assumptions, our method abstracts the system dynamics into a finite stochastic (2.5-player) game graph derived from data. Given a requirement over time on this graph, we compute the winning region -- i.e., the set of initial states from which the objective is satisfiable -- in the resulting game, together with a corresponding control policy. Our main contribution is the construction of abstractions, winning regions and control policies incrementally, as data about the system dynamics accumulates. Concretely, our algorithm refines under- and over-approximations of reachable sets for each state-action pair as new data samples arrive. These refinements induce structural modifications in the game graph abstraction -- such as the addition or removal of nodes and edges -- which in turn modify the winning region. Crucially, we show that these updates are inherently monotonic: under-approximations only grow, over-approximations only shrink, and the winning region only expands. We exploit this monotonicity by defining an objective-induced ranking function on the nodes of the abstract game that increases monotonically as new data samples are incorporated. These ranks underpin our novel incremental game-solving algorithm, which employs customized gadgets (DAG-like subgames) within a rank-lifting algorithm to efficiently update the winning region. Numerical case studies demonstrate significant computational savings compared to the baseline approach, which resolves the entire game from scratch whenever new data samples arrive.

Highlights Conference 2025 Conference Abstract

Fair Energy and Mean-Payoff Games

• Irmak Sağlam

Highlights Conference 2024 Conference Abstract

Fair omega-regular games

• Irmak Sağlam

We consider two-player games over finite graphs in which both players are restricted by fairness constraints on their moves. Given a two player game graph $G=(V, E)$ and a set of fair moves $E_f\subseteq E$ a player is said to play fair in $G$ if they choose an edge $e\in E_f$ infinitely often whenever the source node of $e$ is visited infinitely often. Otherwise, they play unfair. We equip such games with two $\omega$-regular winning conditions $\alpha$ and $\beta$ deciding the winner of mutually fair and mutually unfair plays, respectively. Whenever one player plays fair and the other plays unfair, the fairly playing player wins the game. The resulting games are called fair $\alpha/\beta games. %Further, if $\alpha$ and $\beta$ are given by a parity condition over $G$ they are called fair parity/parity games. We formalize fair $\alpha/\beta$ games and show that they are determined. For fair parity/parity games, i. e. , fair $\alpha/\beta$ games where $\alpha$ and $\beta$ are given each by a parity condition over $G$, we provide a polynomial reduction to (normal) parity games via a gadget construction inspired by the reduction of stochastic parity games to parity games. We further give a direct symbolic fixpoint algorithm to solve fair parity/parity games. On a conceptual level, we illustrate the translation between the gadget-based reduction and the direct symbolic algorithm which uncovers the underlying similarities of solution algorithms for fair and stochastic parity games, as well as for the recently considered class of fair games in which only one player is restricted by fair moves. This presentation is based on joint work with Daniel Hausmann, Nir Piterman and Anne-Kathrin Schmuck, published in FoSSaCS 2024: https: //link. springer. com/chapter/10. 1007/978-3-031-57228-9_2.