🤖 machine learning

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

This paper presents the first positive result for decentralized and private PAC learning in turn-based stochastic games with reachability objectives by introducing a game-theoretic generalization of the Expected Conditional Distance parameter to establish polynomial-sample complexity bounds without requiring shared information or algorithms.

Original authors: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Published 2026-07-17

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach two rival video game characters how to play a new, mysterious board game. One character, let's call him "Max," wants to reach a treasure chest as fast as possible. The other, "Min," wants to stop him, perhaps by leading him into a trap or making him wander in circles forever. This isn't just a simple game of chance; it's a battle of wits where every move changes the odds. In the world of computer science, this is called a "Turn-Based Stochastic Game." It's a fancy way of describing a situation where two opponents take turns making decisions, but the outcome of those decisions involves a roll of the dice.

Usually, when we teach computers to play games, we assume they can see everything: the rules, the board, and what the other player is thinking. But in the real world, things are messier. Often, the computer doesn't know the rules at all; it has to learn them by playing, making mistakes, and seeing what happens. This is called "Reinforcement Learning." The goal is to find a strategy that is "Probably Approximately Correct" (PAC). That's a mouthful, but it simply means: "Can we design a learning method that, after a reasonable amount of practice, will almost certainly find a strategy that is almost as good as the best possible one?"

The tricky part is that for certain types of goals—like "reach the treasure eventually"—learning is mathematically impossible if the game can go on forever and the players are truly adversarial. If the opponent is trying to trick you, they might pretend to help you learn, only to reveal a trap later. This paper tackles a specific, tough version of this problem: Can two players learn to play this game well if they can't talk to each other, can't see each other's moves, and don't know the rules?

The Great Game of Hide-and-Seek with Dice

In this paper, the authors—Ali Asadi, Krishnendu Chatterjee, and Pavol Kebis—take on a challenge that sounds like a paradox. They want to teach two rival players, Max and Min, how to play a game where Max wants to reach a target and Min wants to stop him. The catch? They are playing in the dark. They don't know the rules of the board, they can't share notes, and they don't even know what the other player is doing at any given moment.

In many previous attempts to solve this, researchers made two big, unrealistic assumptions. First, they assumed the players could share a "public notebook" where they wrote down everything they learned. Second, they assumed the players were using the exact same learning algorithm, like two students copying from the same textbook. The authors of this paper say, "Hold on, that's not how the real world works." In reality, players often have private information and use different methods to learn. They wanted to know: Can we still learn to play well if everyone keeps their own secrets and uses their own brain?

The "Waiting Game" Problem

To understand why this is so hard, imagine a game where the treasure is hidden behind a door that opens only once every million years. If the players are just guessing, they might wait forever. In the world of math, this is called an "infinite horizon" problem. If the game can go on forever, and the opponent is smart enough to delay the end, you can never be sure if you're learning the right thing or just waiting for a miracle that might never happen.

The authors realized that for learning to be possible, they needed a safety net. They introduced a concept called the Expected Conditional Distance (ECD). Think of this as a "patience meter" for the game. It measures: "If the target is reachable, how long, on average, does it take to get there?" If the ECD is small, it means the game doesn't drag on forever; the treasure is usually found relatively quickly. If the ECD is huge, it means the game could get stuck in a loop of waiting for an incredibly long time.

The paper proves that if this "patience meter" is bounded (meaning the game doesn't take forever to finish), then learning is possible, even in the dark. They showed that by knowing this number, you can effectively turn the infinite game into a finite one, like cutting off the game after a certain number of moves because you know the treasure would have been found by then. It is important to note that without such an assumption (like ECD, or other similar constraints found in previous literature), learning is impossible in general for these types of games. The paper doesn't claim ECD is the only way, but it is the specific key they used to unlock the problem in this new setting.

The Secret Sauce: Learning in Stages

So, how do they actually teach the players? The authors designed a clever pair of learning algorithms (one for Max, one for Min) that work like a team of explorers mapping a cave.

The Map Expansion: Instead of just thinking about "State A" or "State B," the players imagine a 3D map where the third dimension is "Time." They break the game down into "State-Step" pairs. It's like saying, "At step 1, I'm in the kitchen; at step 2, I'm in the hallway." This helps them plan backwards from the end.
The "Best Arm" Trick: At every single spot on their map, the players have to choose an action. They use a technique from a field called "Bandit Learning" (imagine a gambler trying to find the best slot machine). They try different moves, see which one works best, and stick with it. But they do this with high confidence, making sure they aren't just getting lucky.
The Exploration Loop: The players start by exploring the "unexplored" parts of the map. They treat these unknown spots as new "treasures" to find. Once they figure out the best move for a specific spot, they mark it as "explored" and move on. They keep doing this, building up a strategy step-by-step, until they have a plan for the whole game.
The Private Agreement: Here is the magic. Even though they never talk, they both follow a similar rhythm. They keep playing until they both feel they have explored enough. When neither player can find any new "unexplored" spots in their own private view, they both signal to the game simulator: "We're done! Here is our strategy."

The Result: A New Kind of Learning

The paper's main finding is a resounding "Yes." They proved that with this method, the players can learn a strategy that is almost perfect (within a tiny error margin) with a high probability of success. Crucially, the number of times they need to play the game (the "sample complexity") grows in a manageable, polynomial way. This means the learning time doesn't explode into infinity; it stays reasonable even as the game gets bigger.

This is a big deal because it's the first time anyone has shown that you can learn to play these complex, adversarial games in a decentralized (no shared brain) and private (no shared notes) setting. Before this, people thought you needed to share information to learn effectively. The authors showed that by using the "patience meter" (ECD) and a clever backward-planning strategy, you can learn in the dark.

They also clarified that learning this type of game without additional assumptions (like the ECD bound) is impossible in general. If the game can drag on forever with no limit on how long it takes to reach the target, no learning algorithm can guarantee success. The paper is very clear: you need that bound on time to make the math work.

Why Should You Care?

You might wonder, "Who cares about two players rolling dice in a theoretical game?" Well, this isn't just about board games. This kind of math is the backbone of how we build safe AI for things like self-driving cars, network security, and automated trading. In those real-world scenarios, different systems (or hackers) are constantly interacting, often without full knowledge of what the other is doing.

This paper gives us a new toolkit. It tells us that even if we can't force all our AI agents to share their secrets, and even if they are trying to outsmart each other, we can still teach them to be smart and safe, provided we know that the "bad things" won't happen after an infinite amount of time. It's a step toward building AI that can navigate a chaotic, uncertain world without needing a central boss to tell them what to do.

In short, the authors took a problem that seemed impossible—learning a game in the dark with a rival—and found a way to turn the lights on, one step at a time, using a clever measure of patience and a lot of backward thinking.

Technical Summary: PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

Problem Statement
The paper addresses the problem of Probably Approximately Correct (PAC) learning for Turn-Based Stochastic Games (TBSGs) with reachability objectives. In TBSGs, two adversarial players (Max and Min) interact over a finite state space with stochastic transitions. The objective is for Max to maximize, and Min to minimize, the probability of eventually reaching a target set of states.

The authors highlight a fundamental hardness result: PAC learning for reachability objectives is generally impossible in TBSGs (and even in Markov Decision Processes) without additional assumptions. This impossibility arises because reachability is an unbounded property, and adversarial behavior during the learning phase can render learning futile (e.g., an adversary might choose a suboptimal action that reaches the target immediately, masking the true optimal strategy).

Previous positive results for TBSGs relied on two strong assumptions:

Public Information: Both players share all information (states, actions, transitions).
Centralized Learning: Both players utilize the same learning algorithm.

This work aims to relax these assumptions to achieve learning in a decentralized setting where players use distinct algorithms and possess private information (specifically, the current state is only known to the player owning that state).

Methodology
The proposed approach involves a two-stage reduction and a novel learning algorithm:

Generalization of Expected Conditional Distance (ECD):
The authors introduce a game-theoretic generalization of the Expected Conditional Distance (ECD) parameter, originally defined for MDPs.
- Definition: The ECD of a game is defined as the supremum over all Min strategies of the infimum over Max's best-responses of the expected time to reach the target, conditioned on the target being reached.
- Rationale: Several natural generalizations of ECD to games were shown to fail (e.g., they could be small even when the required horizon for approximation is large). The proposed definition ensures that if the ECD is bounded by $L$ , the infinite-horizon reachability problem can be reduced to a finite-horizon problem with horizon $H \approx 2(L+1)/\epsilon$ . This truncation converts the intractable infinite-horizon problem into a tractable finite-horizon one.
Finite-Horizon Expansion:
To solve the finite-horizon reachability problem, the authors define an expanded game $G'$ . This game unfolds the time horizon into the state space, creating state-step pairs $(s, \ell)$ where $\ell$ represents the current step. This transformation allows the use of backward induction, as the game becomes equivalent to a finite-horizon MDP-like structure where positional strategies are sufficient.
Decentralized Learning Algorithm (LeTuReGa):
The paper presents a pair of algorithms, LeTuReGaMax and LeTuReGaMin, designed for the decentralized private setting.
- Mechanism: The algorithms operate in stages. In each stage, a player constructs a strategy using backward induction from the horizon $L$ down to step 0.
- Local Learning: At each state-step $(s, \ell)$ , the player employs a Best-Arm Identification (BAI) routine to identify an $\epsilon$ -optimal action with high confidence. This avoids the need to estimate the full transition probabilities (which is infeasible in private settings) and instead focuses directly on identifying optimal actions.
- Exploration: The algorithms maintain a set of "unexplored" state-steps. These unexplored sets act as auxiliary target sets to incentivize players to visit new parts of the state-step space.
- Termination: The learning process terminates when both players propose a strategy profile to the simulator, which occurs when neither player can discover new state-steps using their current strategy.

Key Contributions

Decentralized Private PAC-RL: The work provides the first positive result for PAC learning in TBSGs with reachability objectives under decentralized and private information settings. Players do not share algorithms or state information.
ECD Generalization: The paper establishes a subtle and correct generalization of the ECD parameter to TBSGs, proving that a bounded ECD allows for the reduction of infinite-horizon reachability to finite-horizon reachability.
Polynomial Sample Complexity: The authors establish a polynomial sample complexity bound for the proposed algorithms. The complexity depends polynomially on the number of states ( $|S|$ ), actions ( $|A|$ ), the ECD parameter ( $L$ ), and the inverses of the error tolerance ( $1/\epsilon$ ) and failure probability ( $1/p$ ).
Algorithmic Design: The introduction of a learning procedure that combines backward induction, best-arm identification, and dynamic exploration of state-steps without requiring transition probability estimation.

Results
The main theoretical result (Corollary 16) states that the pair of algorithms (LeTuReGaMax, LeTuReGaMin) is PAC-RL for reachability objectives with ECD assumption. The sample complexity is:
$O\left( \frac{|S|^3 L^7 |A| \log(|S|^2 L^2 / (p \epsilon^2))}{\epsilon^{10}} \right)$
where $L$ is the bound on the ECD parameter.

The proof relies on showing that:

The learning simulation terminates within $|S'|$ stages (where $S'$ is the set of expanded states).
With high probability, the constructed strategy profile is $\epsilon$ -optimal for the finite-horizon game.
Due to the ECD bound, the $\epsilon$ -optimality in the finite-horizon game translates to $\epsilon$ -optimality in the original infinite-horizon game.

Significance
The paper claims significance primarily in relaxing the strong assumptions of prior work. Previous PAC learning results for TBSGs required public information and centralized learning. This work demonstrates that learning is possible even when players act independently and possess private state information, provided the ECD parameter is bounded. Furthermore, unlike previous "anytime" algorithms for TBSGs that lacked sample complexity guarantees, this work provides explicit polynomial bounds. The authors note that this is the first positive result for decentralized private information PAC-RL in TBSGs with reachability objectives.