Introduction
Planning under imperfect information requires agents to act from histories rather than from the true state. In partially observable Markov decision processes (POMDPs), belief states restore a Markovian dynamic program and support exact and point-based solvers ([1 , 40 , 43 , 34 , 41 ] ). In partially observable stochastic games (POSGs), partial observability is coupled with strategic uncertainty. Each player must reason about the hidden state, its own information, and the possible information and actions of the other players ([16 , 22 ] ). The two-player zero-sum case, called a zero-sum partially observable stochastic game (zs-POSG), is the adversarial form of this problem. Dynamic programming is classical for fully observable stochastic games ([39 , 15 ] ), but partial observability requires a sufficient statistic for planning. Common-information, plan-time, and occupancy-state reductions provide such statistics for decentralised control and Dec-POMDPs ([27 , 10 , 12 , 30 ] ). Recent work has extended this programme to adversarial settings, including value-structure results, one-sided partially observable stochastic games, public-observation games, and general two-player zs-POSGs ([47 , 18 , 17 , 20 , 5 , 7 , 42 , 14 ] ). In these reductions, a zs-POSG is lifted to an occupancy stochastic game. The lifted state is a distribution over hidden states and histories. The lifted actions are decision rules. The reduced game is fully observed by the planner. It preserves the value of the original game and restores Bellman recursion.
This progress leaves an algorithmic gap. Existing dynamic-programming solvers for zs-POSGs are mostly point-based value-iteration methods ([34 , 41 , 7 , 14 ] ). They approximate the optimal central value on sampled occupancy states and apply Bellman backups, for all samples in sync. This is principled, but it creates a coverage problem. The approximation must support backups over a large occupancy space. Player-specific policy improvement needs accurate value information only where the current policy can fail to be secure. In zero-sum games, these regions are not determined by the current policy alone. They are exposed by unilateral deviations and worst-case responses. The difficulty is therefore not only to extract executable policies from a central planner. It is the mismatch between global value approximation and local policy improvement.
Policy-update methods address another side of the same problem. Fictitious play, counterfactual regret minimisation, and CFR+ update policies directly in imperfect-information games [35 , 50 , 28 , 44 , 25 , 4 ] . Classical fictitious play, regret minimisation, and CFR-style methods show that repeated local improvement can solve large zero-sum imperfect-information games without explicitly representing a global dynamic program [35 , 50 , 28 , 44 ] . Sequence-form methods and information-set decompositions provide compact representations of extensive-form games [21 , 25 , 4 , 22 ] . Policy-improvement and trust-region methods provide another route to executable updates in reinforcement learning and multi-agent reinforcement learning [3 , 26 , 19 , 36 , 37 , 48 , 49 ] . Search and policy improvement have also been combined in cooperative or partially observable multi-agent settings [24 , 45 , 46 , 33 ] . These methods are attractive because they update policies at histories or information states that are executable by construction.
Existing methods provide either a principled value equation or executable policy updates. They do not yet provide both in a form suited to focused approximation. The central occupancy reduction provides a Bellman equation, but its state is broad and not directly executable. Focal planning makes policy extraction player-specific, but its state is set-valued and lacks a tractable value representation. Policy-space methods update executable policies, but they do not provide a Bellman representation for focused point-based backups. The missing object is therefore a player-specific value representation that keeps executable decision rules while supporting local Bellman backups.
To address this gap, we introduce Conservative Policy Iteration (CPI) for finite-horizon zs-POSGs. CPI maintains one policy per player and improves both policies along occupancy trajectories induced by conservative policy updates. For each player, the current policy induces a value function in the corresponding player-specific planning process. CPI uses this policy-induced value function for local Bellman backups, instead of constructing a global central value function. Each backup computes an improved decision rule for one player from its current value function. The two policies are updated together, so the opposing policy used during rollouts is supplied by the other player-specific planning process. The improved decision rules are averaged into the current policies, and GLIE perturbations maintain exploration. Thus, updates are performed where the current joint policy is tested by adversarial interaction, rather than by uniformly covering the central occupancy space. The convergence guarantees are conditional on exact local backups, sufficient coverage, and the stated regularity assumptions. We evaluate CPI on standard finite-horizon zero-sum POSG benchmarks. The method is competitive at small horizons. At larger horizons, it often improves the runtime-exploitability trade-off compared with PBVI [14 ] , HSVI [7 ] , and CFR+ [44 ] .
Preliminaries
Finite-horizon zero-sum POSGs are stochastic games with hidden states and imperfect information.
Definition 1. A finite-horizon zero-sum partially observable stochastic game (zs-POSG) is a tuple M = ( I , S , A , Z , Z 0 , p , ( r i ) i ∈ I , T , b 0 ) \mathcal{M} = (\mathcal{I},\mathcal{S},\mathcal{A},\mathcal{Z},\mathcal{Z}^{0},p,(r^{i})_{i\in\mathcal{I}},T,b_{0}) M = ( I , S , A , Z , Z 0 , p , ( r i ) i ∈ I , T , b 0 ) , where I = { 1 , 2 } \mathcal{I} = \{1,2\} I = { 1 , 2 } , S \mathcal{S} S is a finite state space, A = × i ∈ I A i \mathcal{A} = \times_{i\in\mathcal{I}}\mathcal{A}^{i} A = × i ∈ I A i is the joint action space, Z = × i ∈ I Z i \mathcal{Z} = \times_{i\in\mathcal{I}}\mathcal{Z}^{i} Z = × i ∈ I Z i is the joint private observation space, Z 0 \mathcal{Z}^{0} Z 0 is the public observation space, p : S × A × Z 0 × Z → S p:\mathcal{S}\times\mathcal{A}\times\mathcal{Z}^{0}\times\mathcal{Z}\to\mathcal{S} p : S × A × Z 0 × Z → S is the transition kernel, r i : S × A → R r^{i}:\mathcal{S}\times\mathcal{A}\to\mathbb{R} r i : S × A → R is player i i i ’s reward, r 2 = − r 1 r^{2}=-r^{1} r 2 = − r 1 , b 0 ∈ Δ ( S ) b_{0}\in\Delta(\mathcal{S}) b 0 ∈ Δ ( S ) is the initial state distribution, and T T T is the horizon.
The game unfolds over stages t = 0 , … , T − 1 t = 0,\ldots,T-1 t = 0 , … , T − 1 . At stage t t t , the players choose a t a_t a t , each player i i i receives r i ( s t , a t ) r^{i}(s_t,a_t) r i ( s t , a t ) , and the game samples ( s t + 1 , z t + 1 0 , z t + 1 ) (s_{t+1},z^{0}_{t+1},z_{t+1}) ( s t + 1 , z t + 1 0 , z t + 1 ) according to p ( ⋅ ∣ s t , a t ) p(\cdot\mid s_t,a_t) p ( ⋅ ∣ s t , a t ) . Because the state is hidden, i i i acts from its private history h t i h^{i}_{t} h t i and the public history h t 0 h^{0}_{t} h t 0 . These histories are empty at t = 0 t=0 t = 0 . For t ≥ 1 t\geq1 t ≥ 1 , h t i = a 0 i z 1 i ⋯ a t − 1 i z t i h^{i}_{t}=a^{i}_{0}z^{i}_{1}\cdots a^{i}_{t-1}z^{i}_{t} h t i = a 0 i z 1 i ⋯ a t − 1 i z t i records i i i ’s past actions and private observations, and h t 0 = z 1 0 ⋯ z t 0 h^{0}_{t}=z^{0}_{1}\cdots z^{0}_{t} h t 0 = z 1 0 ⋯ z t 0 records the public observations. We write h t = ( h t 1 , h t 2 ) h_t=(h^{1}_{t},h^{2}_{t}) h t = ( h t 1 , h t 2 ) for a joint private history, with reachable sets H t i \mathcal{H}^{i}_{t} H t i , H t \mathcal{H}_{t} H t , and H t 0 \mathcal{H}^{0}_{t} H t 0 .
A decision rule for player i i i is a map π t i : H t i × H t 0 → Δ ( A i ) \pi_t^i : \mathcal{H}_t^i \times\mathcal{H}_t^0 \to\Delta(\mathcal{A}_i) π t i : H t i × H t 0 → Δ ( A i ) . A joint decision rule is π t = ( π t 1 , π t 2 ) ∈ Π t ≔ Π t 1 × Π t 2 \pi_t = (\pi_t^1,\pi_t^2) \in\Pi_t \coloneqq\Pi_t^1 \times\Pi_t^2 π t = ( π t 1 , π t 2 ) ∈ Π t : = Π t 1 × Π t 2 . A behavioural policy profile is π = ( π 0 , … , π T − 1 ) ∈ Π \pi= (\pi_0,\ldots,\pi_{T-1}) \in\Pi π = ( π 0 , … , π T − 1 ) ∈ Π . We write π i ∈ Π i \pi^i \in\Pi^i π i ∈ Π i for a full behavioural policy of player i i i . We write π t : T i ∈ Π t : T i \pi_{t:T}^i \in\Pi_{t:T}^i π t : T i ∈ Π t : T i for player i i i ’s policy suffix and π t : T ∈ Π t : T \pi_{t:T} \in\Pi_{t:T} π t : T ∈ Π t : T for a policy-profile suffix from stage t t t onward. We write π 0 : t i ∈ Π 0 : t i \pi_{0:t}^i \in\Pi_{0:t}^i π 0 : t i ∈ Π 0 : t i for player i i i ’s policy prefix and π 0 : t ∈ Π 0 : t \pi_{0:t} \in\Pi_{0:t} π 0 : t ∈ Π 0 : t for a policy-profile prefix.
Policies are evaluated by expected cumulative payoff. Given b 0 b_0 b 0 , i i i ’s payoff under π \pi π is J i π ≔ E b 0 , p , π [ ∑ k = 0 T − 1 r i ( S k , A k ) ] J_i^\pi\coloneqq\mathbb{E}_{b_0,p,\pi}\left[\sum_{k=0}^{T-1} r^i(S_k,A_k)\right] J i π : = E b 0 , p , π [ ∑ k = 0 T − 1 r i ( S k , A k ) ] . Since r 2 = − r 1 r^2=-r^1 r 2 = − r 1 , we write the zero-sum game from player 1’s perspective. The finite-horizon zs-POSG induces a finite zero-sum extensive-form game with perfect recall, so the classical minimax and behavioural-policy foundations apply [29 , 23 ] . Thus,
v 0 1 , ∗ ( b 0 ) = max π 1 ∈ Π 1 min π 2 ∈ Π 2 J 1 ( π 1 , π 2 ) = min π 2 ∈ Π 2 max π 1 ∈ Π 1 J 1 ( π 1 , π 2 ) . v_0^{1,*}(b_0)=\max_{\pi^1\in\Pi^1}\min_{\pi^2\in\Pi^2}J_1^{(\pi^1,\pi^2)}=\min_{\pi^2\in\Pi^2}\max_{\pi^1\in\Pi^1}J_1^{(\pi^1,\pi^2)}. v 0 1 , ∗ ( b 0 ) = π 1 ∈ Π 1 max π 2 ∈ Π 2 min J 1 ( π 1 , π 2 ) = π 2 ∈ Π 2 min π 1 ∈ Π 1 max J 1 ( π 1 , π 2 ) .
A policy profile attaining this value is a Nash equilibrium of the induced zero-sum game. Equivalently, player i i i ’s component is maximin optimal for i i i ’s payoff for any i ∈ I i \in\mathcal{I} i ∈ I . This player-specific view is central below. A value-based method must ultimately select decision rules that can be implemented from each player’s private and public information.
Occupancy-state dynamic programming
Bellman recursion relies on a state that is sufficient for the continuation problem. For a policy-profile prefix π 0 : t \pi_{0:t} π 0 : t , the central occupancy state is o t ( π 0 : t ) = P b 0 , p , π 0 : t ( S t , H t , H t 0 ) o_t(\pi_{0:t})=\mathbb{P}_{b_0,p,\pi_{0:t}}(S_t,H_t,H_t^0) o t ( π 0 : t ) = P b 0 , p , π 0 : t ( S t , H t , H t 0 ) . We write o t o_t o t when the prefix is clear. It belongs to O t ⊆ Δ ( S × H t × H t 0 ) \mathcal{O}_t \subseteq\Delta(\mathcal{S}\times\mathcal{H}_t\times\mathcal{H}_t^0) O t ⊆ Δ ( S × H t × H t 0 ) . Although o t o_t o t is not observed by either player, it is Markovian for a central planner. Given o t o_t o t and π t \pi_t π t , the next occupancy is τ t ( o t , π t ) = P o t , π t ( S t + 1 , H t + 1 , H t + 1 0 ) \tau_t(o_t,\pi_t)=\mathbb{P}_{o_t,\pi_t}(S_{t+1},H_{t+1},H_{t+1}^0) τ t ( o t , π t ) = P o t , π t ( S t + 1 , H t + 1 , H t + 1 0 ) . Player i i i ’s one-step expected reward is ρ i , t ( o t , π t ) = E o t , π t [ r i ( S t , A t ) ] \rho_{i,t}(o_t,\pi_t)=\mathbb{E}_{o_t,\pi_t}[r^i(S_t,A_t)] ρ i , t ( o t , π t ) = E o t , π t [ r i ( S t , A t )] .
The central occupancy state restores Bellman’s principle for the zero-sum value. With v T 1 , ∗ ( ⋅ ) = 0 v_T^{1,*}(\cdot)=0 v T 1 , ∗ ( ⋅ ) = 0 , the central dynamic program is
v t 1 , ∗ ( o t ) = N E ( π t 1 , π t 2 ) { ρ 1 , t ( o t , π t ) + v t + 1 1 , ∗ ( τ t ( o t , π t ) ) } . v_t^{1,*}(o_t)=NE_{(\pi_t^1,\pi_t^2)}\{\rho_{1,t}(o_t,\pi_t)+v_{t+1}^{1,*}(\tau_t(o_t,\pi_t))\}. v t 1 , ∗ ( o t ) = N E ( π t 1 , π t 2 ) { ρ 1 , t ( o t , π t ) + v t + 1 1 , ∗ ( τ t ( o t , π t ))} .
where N E NE N E denotes the operator that returns the value associated to the Nash equilibrium of the corresponding subgame.
This recursion is the basis of exact and approximate occupancy-based planning methods for Dec-POMDPs and zs-POSGs (Dibangoye et al., 2012; 2013; 2014; 2016b;a; Dibangoye & Buffet, 2018; Delage et al., 2023; Peralez et al., 2025; 2024; Escudie et al., 2025). The difficulty is not the recursion itself, but the space on which it acts. The number of coordinates needed to represent o t o_t o t grows exponentially with the horizon. Point-based value iteration is a natural approximation paradigm for such continuous-state dynamic programs, but its zs-POSG instantiations provide limited guidance on where to place samples [34 , 41 , 38 , 7 , 14 ] .
The central planner game provides the correct value equation and, in principle, produces the optimal decision rules. The difficulty is instead computational: the central occupancy state induces a very large decision space. In particular, solving the corresponding subgame requires optimizing over decision rules defined on the possible central states, which can be viewed as a large matrix whose rows correspond to decision rules. This representation quickly becomes intractable as the horizon and information spaces grow.
The challenge lies in exploiting the decision rules produced by the central formulation without having to explicitly enumerate or sample the entire central occupancy space. In particular, we seek a representation that retains the correct Bellman recursion while allowing the relevant parts of the decision-rule space to be explored efficiently.
Focal Belief Games
We rewrite the central state by conditioning on the information relevant to the focal player i i i and on the policies that determine the other players’ behaviour. More precisely, we condition on the public history, the opponent’s private history, and the focal player’s policy prefix. This representation allows us to separate two steps of the solution procedure. First, during policy evaluation, we fix the focal player’s current policy and compute the value it can guarantee against an opponent that best responds to it. This gives a pessimistic continuation value for the focal player’s policy. Second, during policy improvement, this continuation value is used to determine a better decision rule for the focal player at the current stage, in the same spirit as a Bellman backup.
Figure 1. The optimal value function of the game M i \mathcal{M}^{i} M i is convex in the belief space. While value-iteration methods such as PBVI sample this space and operate on a set of vectors to represent v ‾ i , t \underline{v}_{i,t} v i , t , our method works with a single vector v ‾ i , t π t : T i \underline{v}_{i,t}^{\pi^{i}_{t:T}} v i , t π t : T i at a time, reducing the complexity of the associated algorithms.
Conditional occupancy states
Fix focal player i i i . At stage t t t , fix the public history h t 0 h_t^0 h t 0 , the opponent private history h t − i h_t^{-i} h t − i , and the focal policy prefix π 0 : t i \pi_{0:t}^i π 0 : t i . Conditioning the central occupancy state on these variables gives the conditional occupancy state
c t i ( h t 0 , h t − i , π 0 : t i ) ≔ P b 0 , p ( S t , H t i ∣ H t 0 = h t 0 , H t − i = h t − i , π 0 : t i ) . c_t^i(h_t^0,h_t^{-i},\pi_{0:t}^i) \coloneqq\mathbb{P}_{b_0,p}\left(S_t,H_t^i \mid H_t^0=h_t^0,H_t^{-i}=h_t^{-i},\pi_{0:t}^i\right). c t i ( h t 0 , h t − i , π 0 : t i ) : = P b 0 , p ( S t , H t i ∣ H t 0 = h t 0 , H t − i = h t − i , π 0 : t i ) .
We write c t i c_t^i c t i when the histories and prefix are clear. It is a distribution over the hidden state and the focal player’s private history. If the conditioning event has probability zero, the conditional update is fixed arbitrarily.
Let C t i C_t^i C t i be the set of reachable conditional occupancy states at stage t t t . In this conditional representation, the opponent’s plan-time decision rule is written as π t − i : C t i → A − i \pi_t^{-i}: C_t^i \to A^{-i} π t − i : C t i → A − i , with space Π t − i \Pi_t^{-i} Π t − i . It does not denote an execution-time policy of the original zs-POSG. We use this representation for fixed-policy evaluation and improvement. For fixed-policy evaluation, pure opponent actions are sufficient: after fixing the focal player’s policy suffix, the objective is affine in the opponent’s mixed action, i.e., in its distribution over A − i A^{-i} A − i . Hence, the minimum over mixed actions is attained by a pure action.
Given c t i c_t^i c t i , π t i \pi_t^i π t i , and a t − i a_t^{-i} a t − i , the model induces a probability kernel p i , t c ( ⋅ ∣ c t i , π t i , a t − i ) p_{i,t}^c(\cdot\mid c_t^i,\pi_t^i,a_t^{-i}) p i , t c ( ⋅ ∣ c t i , π t i , a t − i ) on C t + 1 i C_{t+1}^i C t + 1 i . This kernel is obtained by conditioning on the next public observation and the next opponent private observation. The conditional Bayes update and its observation likelihood are denoted by τ i , t c \tau_{i,t}^c τ i , t c and w i , t c w_{i,t}^c w i , t c , and are given in Appendix § 8 .§ 1 . The one-step conditional payoff is g i , t c ( c t i , π t i , a t − i ) g_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i}) g i , t c ( c t i , π t i , a t − i ) .
For a fixed focal policy suffix π t : T i \pi_{t:T}^i π t : T i , these objects define the ingredients for a fixed-policy evaluation. The policy suffix induces a decision rule π k i \pi_k^i π k i at every stage k ≥ t k \ge t k ≥ t . With terminal value v i , T ≡ 0 v_{i,T} \equiv0 v i , T ≡ 0 , the fixed-policy value function satisfies
v i , k : T π i ( c k i ) = min a k − i [ g i , k c ( c k i , π k i , a k − i ) + ∑ c k + 1 i ∈ C k + 1 i p i , k c ( c k + 1 i ∣ c k i , π k i , a k − i ) v i , k + 1 : T π i ( c k + 1 i ) ] . v_{i,k:T}^{\pi^i}(c_k^i)=\min_{a_k^{-i}}\left[g_{i,k}^c(c_k^i,\pi_k^i,a_k^{-i})+\sum_{c_{k+1}^i\in C_{k+1}^i}p_{i,k}^c(c_{k+1}^i\mid c_k^i,\pi_k^i,a_k^{-i})v_{i,k+1:T}^{\pi^i}(c_{k+1}^i)\right]. v i , k : T π i ( c k i ) = a k − i min g i , k c ( c k i , π k i , a k − i ) + c k + 1 i ∈ C k + 1 i ∑ p i , k c ( c k + 1 i ∣ c k i , π k i , a k − i ) v i , k + 1 : T π i ( c k + 1 i ) .
This recursion evaluates a fixed focal policy suffix by accumulating one-step conditional payoffs. It is the value function used later as the continuation term in local policy improvement.
The focal belief game
We now lift the conditional occupancy states to distributions over such states. This gives the player-specific planning state used below.
Fix a focal player i i i . The distribution over conditional occupancy state induced at stage t t t the focal belief. A focal belief b t i ∈ B t i b_t^i \in\mathcal{B}_t^i b t i ∈ B t i is a probability distribution over C t i \mathcal{C}_t^i C t i . Given b t i b_t^i b t i , the focal player chooses π t i \pi_t^i π t i . The opponent’s rule is represented in the conditional coordinates by π t − i \pi_t^{-i} π t − i . The transition τ t i \tau_t^i τ t i is the law of the next focal belief under ( b t i , π t i , π t − i ) (b_t^i,\pi_t^i,\pi_t^{-i}) ( b t i , π t i , π t − i ) . The reward g t i g_t^i g t i is the expected conditional payoff under the same belief and decision rules. Both are given in Appendix § 8 .§ 2 .
Definition 2. M i ≔ ( I , ( B t i ) t = 0 T , ( Π t i ) t = 0 T − 1 , ( Π t − i ) t = 0 T − 1 , ( τ t i ) t = 0 T − 1 , ( g t i ) t = 0 T − 1 , b 0 i , T ) \mathcal{M}^i \coloneqq(\mathcal{I},(\mathcal{B}_t^i)_{t=0}^{T},(\Pi_t^i)_{t=0}^{T-1},(\Pi_t^{-i})_{t=0}^{T-1},(\tau_t^i)_{t=0}^{T-1},(g_t^i)_{t=0}^{T-1},b_0^i,T) M i : = ( I , ( B t i ) t = 0 T , ( Π t i ) t = 0 T − 1 , ( Π t − i ) t = 0 T − 1 , ( τ t i ) t = 0 T − 1 , ( g t i ) t = 0 T − 1 , b 0 i , T ) is the focal belief game associated with the original game M \mathcal{M} M .
The focal belief game is fully observed at the planning level. It is not a strict lossless reduction of the original zs-POSG M \mathcal{M} M . The opponent’s decision problem is represented in conditional coordinates and can therefore be viewed as a virtual player. Fixed-policy value function have the value in both representations, and the focal decision-rule space is unchanged. The problem is inherently one-sided: we fix the policy of a focal player and evaluate how well this player performs against an opponent that minimizes the remaining payoff. For a fixed focal policy suffix π t : T i \pi_{t:T}^i π t : T i , let v i , t π t : T i ( b t i ) v_{i,t}^{\pi_{t:T}^i}(b_t^i) v i , t π t : T i ( b t i ) denote the value obtained from b t i b_t^i b t i when player i i i follows π t : T i \pi_{t:T}^i π t : T i and the opponent chooses actions to minimize the remaining payoff. This one-sided fixed-policy value function is the value function used by CPI.
Structure of the focal belief value
The focal belief game reveals structural properties of the value function that are not explicit in the set-valued focal state representation, as the theorem below states. In particular, the fixed-policy value function v i , t π t : T i v_{i,t}^{\pi_{t:T}^i} v i , t π t : T i defines a linear function over the belief space B t i \mathcal{B}_t^i B t i .
Theorem 1. For any fixed focal policy suffix π t : T i \pi_{t:T}^i π t : T i , the function v i , t π t : T i v_{i,t}^{\pi_{t:T}^i} v i , t π t : T i is linear on B t i \mathcal{B}_t^i B t i and satisfies
v i , t π t : T i ( b t i ) = ∑ c t i ∈ supp ( b t i ) b t i ( c t i ) v i , t π t : T i ( c t i ) . v_{i,t}^{\pi_{t:T}^i}(b_t^i) = \sum_{c_t^i \in\operatorname{supp}(b_t^i)} b_t^i(c_t^i) v_{i,t}^{\pi_{t:T}^i}(c_t^i). v i , t π t : T i ( b t i ) = c t i ∈ supp ( b t i ) ∑ b t i ( c t i ) v i , t π t : T i ( c t i ) .
Although beliefs b t i b_t^i b t i typically have sparse support, their representation remains intractable due to the continuous nature of the conditional state space C t i \mathcal{C}_t^i C t i . Nevertheless, this complexity can be mitigated: the value function induced by a policy π t : T i \pi_{t:T}^i π t : T i can be exactly characterized using a reduced representation, relying only on a subset of relevant components.
Proposition 1. For any fixed focal policy suffix π t : T i \pi_{t:T}^i π t : T i , v i , t π t : T i v_{i,t}^{\pi_{t:T}^i} v i , t π t : T i is piecewise linear and concave on B t i \mathcal{B}_t^i B t i . That is, there exists a finite collection Λ i , t π t : T \Lambda_{i,t}^{\pi_{t:T}} Λ i , t π t : T of α \alpha α -vectors α i , t π t : T ∈ R S t × H t i \alpha_{i,t}^{\pi_{t:T}} \in\mathbb{R}^{S_t \times H_t^i} α i , t π t : T ∈ R S t × H t i , each defining a linear function over the ConditionalSpace space C t i \mathcal{C}_t^i C t i , such that:
v i , t π t : T i ( c t i ) = min α i , t π t : T i ∈ Λ i , t π t : T i α i , t π t : T i ⋅ c t i . v_{i,t}^{\pi_{t:T^i}}(c_t^i) = \min_{\alpha_{i,t}^{\pi_{t:T}^i} \in\Lambda_{i,t}^{\pi_{t:T}^i}} \alpha_{i,t}^{\pi_{t:T}^i} \cdot c_t^i. v i , t π t : T i ( c t i ) = α i , t π t : T i ∈ Λ i , t π t : T i min α i , t π t : T i ⋅ c t i .
Conservative Policy Iteration
We describe Conservative Policy Iteration (CPI) for finite-horizon zs-POSGs. CPI maintains one behavioural policy per player. At each iteration, these policies generate an occupancy trajectory after conservative averaging and GLIE exploration. For each player, it evaluates the current policy through the fixed-policy value function of § 3 . The resulting value function is used as the continuation term in a local Bellman backup. The backup returns an improved decision rule for the focal player. This rule is averaged into the current policy instead of being installed directly. CPI therefore performs local policy improvement along sampled occupancy trajectories. It does not construct the optimal value function of the focal belief game. It also does not attempt to cover the full central occupancy space.
Local policy improvement
Fix a stage t t t , a focal belief b t i b_t^i b t i , and a current focal policy suffix π t + 1 : T i \pi_{t+1:T}^i π t + 1 : T i . The fixed-policy value function v i , t + 1 π t + 1 : T i v_{i,t+1}^{\pi_{t+1:T}^i} v i , t + 1 π t + 1 : T i is used as the continuation value function after stage t t t . We write q ^ i , t \hat{q}_{i,t} q ^ i , t for the corresponding local Q-value, defined by q ^ i , t ( b t i , π t ) ≔ g t i ( b t i , π t ) + v i , t + 1 π t + 1 : T i ( τ t i ( b t i , π t ) ) \hat{q}_{i,t}(b_t^i,\pi_t) \coloneqq g_t^i(b_t^i,\pi_t) + v_{i,t+1}^{\pi_{t+1:T}^i}\left(\tau_t^i(b_t^i,\pi_t)\right) q ^ i , t ( b t i , π t ) : = g t i ( b t i , π t ) + v i , t + 1 π t + 1 : T i ( τ t i ( b t i , π t ) ) .
Algorithm 1 Conservative policy iteration.
1: Initialise $(\Lambda_{i,t})_{t\in\{0,\ldots,T\},i\in\mathcal{I}}$
2: Initialise $(\alpha_k)_{k\ge 0},(\epsilon_k)_{k\ge 0}, k\leftarrow 0$
3: Initialise $(\bar{\pi}_{i,t},u_{i,t})_{t\in\{0,\ldots,T-1\},i\in\mathcal{I}}$
4: while not converged do
5: Recurse$(o_0,k)$
6: $\pi^i_t\leftarrow\tilde{\pi}_{i,t},\ \forall t\in\{0,\ldots,T-1\}$
7: $k\leftarrow k+1$
8: end while
9:
10: Function CGLIE$(\pi^i_t,k)$:
11: $\bar{\pi}_{i,t}\leftarrow(1-\alpha_k)\bar{\pi}_{i,t}+\alpha_k\pi^i_t$
12: return $(1-\epsilon_k)\bar{\pi}_{i,t}+\epsilon_k u_{i,t}$
1: Function Recurse$(o_t,k)$:
2: if $t<T$ then
3: Recurse$(\tau_t(o_t,(\pi^1_t,\pi^2_t)),k)$
4: $\pi^i_t\leftarrow\operatorname{LP}(\operatorname{BELIEF}_i(o_t),\Lambda_{i,t+1}),\ \forall i\in\mathcal{I}$
5: $\tilde{\pi}_{i,t}\leftarrow\operatorname{CGLIE}(\pi^i_t,k),\ \forall i\in\mathcal{I}$
6: $\Lambda_{i,t}\leftarrow\operatorname{VECTOR}(\tilde{\pi}_{i,t}),\ \forall i\in\mathcal{I}$
7: end if
8:
9: Function BELIEF$_i(o_t)$:
10: return $\mathbb{P}_{o_t}(C^i_t)$
The Bellman backup at ( t , b t i ) (t,b^i_t) ( t , b t i ) induces a local zero-sum continuation game, i.e., the finite zero-sum game rooted at ( t , b t i ) (t,b^i_t) ( t , b t i ) with a fixed-policy value function. The focal player chooses a decision rule π t i \pi^i_t π t i . The opponent chooses a decision rule π t − i \pi^{-i}_t π t − i on conditional states. The payoff is q ^ i , t ( b t i , ( π t i , π t − i ) ) \hat{q}_{i,t}(b^i_t,(\pi^i_t,\pi^{-i}_t)) q ^ i , t ( b t i , ( π t i , π t − i )) . We denote this local continuation game by M t i ( q ^ i , t ( b t i , ⋅ ) ) \mathcal{M}^i_t(\hat{q}_{i,t}(b^i_t,\cdot)) M t i ( q ^ i , t ( b t i , ⋅ )) . We write M t i \mathcal{M}^i_t M t i when the continuation value is clear from context.
Definition 3. Tuple M t i = ( I , Π t i , Π t − i , q ^ i , t ( b t i , ⋅ ) ) \mathcal{M}^i_t=(\mathcal{I},\Pi^i_t,\Pi^{-i}_t,\hat{q}_{i,t}(b^i_t,\cdot)) M t i = ( I , Π t i , Π t − i , q ^ i , t ( b t i , ⋅ )) is the finite zero-sum game with players I \mathcal{I} I , action spaces Π t i \Pi^i_t Π t i and Π t − i \Pi^{-i}_t Π t − i , and payoff q ^ i , t ( b t i , ⋅ ) \hat{q}_{i,t}(b^i_t,\cdot) q ^ i , t ( b t i , ⋅ ) .
Revisiting stage t t t at another belief therefore defines another local continuation game. It does not perturb the previous one. For fixed q ^ i , t \hat{q}_{i,t} q ^ i , t , the local backup at b t i b^i_t b t i is max π t i min π t − i q ^ i , t ( b t i , ( π t i , π t − i ) ) \max_{\pi^i_t}\min_{\pi^{-i}_t}\hat{q}_{i,t}(b^i_t,(\pi^i_t,\pi^{-i}_t)) max π t i min π t − i q ^ i , t ( b t i , ( π t i , π t − i )) . This is the local Bellman optimisation problem represented by M t i ( q ^ i , t ( b t i , ⋅ ) ) \mathcal{M}^i_t(\hat{q}_{i,t}(b^i_t,\cdot)) M t i ( q ^ i , t ( b t i , ⋅ )) . A local solution is a max–min optimal focal decision rule together with an opponent minimising decision rule (see Theorem 6 ). Since histories, observations, and actions are finite, deterministic local decision rules are finite. The focal planner may commit to mixed decision rules. The opponent admits deterministic minimising decision rules because the local payoff is affine in its mixed rule.
Conservative Policy Iteration
We now introduce conservative policy iteration (CPI). The algorithm alternes central occupancy expansion with local policy improvement in the two player-specific conditional representations. Algorithm 1 maintains a fixed-policy value representation, step sizes, and averaged decision rules for both players; see Lines 1–3. Each iteration starts from the initial central occupancy state o 0 o_0 o 0 and calls Recurse; see Line 5. The recursion propagates the central occupancy state because the joint policy acts on the original zs-POSG. Line 3 expands then central occupancy state using the current joint decision rule. At each reached o t o_t o t , Line 10 constructs, for each player i i i , the focal belief induced by conditioning o t o_t o t in player i i i ’s basis. Line 4 applies the LP backup (see Theorem 6 ) at this focal belief and returns an improved decision rule for each player. Line 11–12 average the improved decision rule into the current decision rule and add GLIE exploration. GLIE is used to ensure that all components of the belief remain represented. Without exploration, the policy may assign zero probability to some actions, causing the induced belief to become degenerate and eliminating support from parts of the distribution. Maintaining exploration therefore prevents components of the belief from vanishing entirely, similarly to the distribution restart mechanism used in Kakade & Langford [19 ] . Line 6 computes the vector associated with the decision rule just computed, as established by Proposition 1.
Linear program. For a reached belief b t i b^i_t b t i , the local LP is written at the conditional level. The input Λ i , t + 1 \Lambda_{i,t+1} Λ i , t + 1 denotes the stored lower envelop of α \alpha α -vectors representing the fixed-policy value function used for the continuation term. The LP implements the local backup in M t i \mathcal{M}^i_t M t i , cf. Appendix § 8 .6.1. In Algorithm 1, LP ( b t i , λ i , t + 1 ) \operatorname{LP}(b^i_t,\lambda_{i,t+1}) LP ( b t i , λ i , t + 1 ) denotes this local policy-improvement routine.
Theorem 2. Let the policy updates of player i i i be given by
π i , k + 1 = ( 1 − α k ) π i , k + α k F ~ i ( π i , k , π − i , k ) + U i , k + 1 , (1) \pi^{i,k+1}=(1-\alpha_k)\pi^{i,k}+\alpha_k\tilde{F}^i(\pi^{i,k},\pi^{-i,k})+U_{i,k+1}, \tag*{(1)} π i , k + 1 = ( 1 − α k ) π i , k + α k F ~ i ( π i , k , π − i , k ) + U i , k + 1 , (1)
where F ~ i \widetilde{F}^{i} F i represents all the stage-wise policy optimization operator F ~ t i \widetilde{F}^{i}_{t} F t i obtained from the corresponding LP (Line 4 in Algorithm 1), and U i , k + 1 U_{i,k+1} U i , k + 1 is a noise term. Assume that the step sizes satisfy the Robbins-Monro conditions
∑ k = 0 ∞ α k = ∞ , ∑ k = 0 ∞ α k 2 < ∞ . \sum_{k=0}^{\infty} \alpha_k = \infty,\qquad\sum_{k=0}^{\infty} \alpha_k^2 < \infty. k = 0 ∑ ∞ α k = ∞ , k = 0 ∑ ∞ α k 2 < ∞.
Under the standard stochastic approximation conditions on U i , k U_{i,k} U i , k and the approximation error between the discrete operator F ~ i \widetilde{F}^{i} F i and the continuous dynamics F i F^{i} F i (see Definition 4), the algorithm converges almost surely to the set of Nash equilibria.
Theorem 2 establishes the convergence of Algorithm 1, since its discrete update operator coincides with the operator defined in the algorithm. The GLIE noise introduced during exploration does not affect this convergence result, as it satisfies the conditions required by the convergence theorem.
Empirical Evaluation
We evaluate CPI on standard finite-horizon zero-sum POSG benchmarks: Adversarial Tiger , Recycling , Mabc , and Matching Pennies . Benchmark descriptions are available at http://masplan.org/ . Some instances originate from common-payoff problems and are converted to the zero-sum setting by negating player 1’s payoff for player 2. We compare CPI with PBVI (Escudie et al., [14 ] ), HSVI (Delage et al., [7 ] ) and CFR+(Zinkevich et al., [50 ] ; Tammelin [44 ] ). The CFR+ base-line adapts the extensive-form game CFR+ directly to the occupancy-state reduction of zs-POSGs; implementation details are given in Appendix D.§ 1 . In contrast, our CFR+ formulation naturally leverages the objects introduced in this paper, further strengthening the theoretical contribution of the paper. In particular, the POSG setting provides a compact representation of histories and occupancy states that can be exploited to speed up CFR. This allows CFR+ to reason directly over clusters of probabilistically equivalent private histories, rather than operating on the significantly larger extensive-form representation. All methods are evaluated on the same finite-horizon POSG instances. Table 1 reports runtime, value, and exploitability. Results for extensive-form games are discussed solely in Appendix § 11 .
Table 1. Snapshot of the empirical results, including the computational cost of exploitability evaluation. For each game, horizon and algorithm, we report time, value and exploitability ϵ \epsilon ϵ associated with the computed ϵ \epsilon ϵ -Nash equilibrium. OOT occurs when the target exploitability threshold cannot be reached within the prescribed time limit, while OOM means that the algorithms ran out of memory. magenta = lowest exploitability/value per benchmark
CPI vs PBVI. CPI is competitive with PBVI at small horizons and improves the runtime–exploitability trade-off at larger horizons. Indeed, PBVI grows exponentially with the horizon, as it adds an exponentially increasing number of occupancy states by construction. This difference is particularly visible in games such as Matching Pennies (T = 25 , 50 T = 25, 50 T = 25 , 50 in Table 1 and Figure 2 ), where PBVI is sensitive to the sampled belief set. For instance, insufficient or poorly distributed samples may slow convergence or degrade the quality of its central value function approximation. This sensitivity is particularly relevant because exploitability is approximated in our experiments: PBVI must converge to sufficiently low exploitability for this approximation to provide a reliable indication of safety, so a temporary increase in measured exploitability can indicate that the policy remains exploitable. In contrast, CPI updates policies along trajectories induced by the current conservative joint policy, which can guide updates toward regions where the policies are still exploitable. From a computational perspective, PBVI applies a relatively expensive backup operator over a growing collection of sampled belief points. As the horizon increases, maintaining and updating this point set becomes prohibitive. CPI instead performs local policy updates along sampled trajectories, avoiding the explicit construction of large point sets. In our experiments, this generally resulted in more stable scaling behaviour (Section A.7).
Figure 2. Evolution of value and exploitability across different games under a fixed horizon ℓ = 5 \ell= 5 ℓ = 5 . The results compare three methods: CFR+ , PBVI , and CPI , highlighting their respective performance profiles in terms of convergence behaviour and solution quality across the considered benchmarks.
Finally, although CPI and CFR+ outperform PBVI for higher horizon, PBVI achieves stronger results on Adversarial Tiger and Recycling (see Figure 2 ). Adversarial Tiger is particularly well suited to methods that cover a broader occupancy space such as point-based value iteration algorithms. Notably, computation time increases proportionally with the horizon for CPI, whereas PBVI’s computation time may vary depending on the sampling, as observed for Recycling in Table 1 .
CPI vs CFR. Both CPI and CFR-based methods improve policies iteratively, but through different update mechanisms. In our experiments, CFR iterations are computationally cheaper than CPI updates. However, exploitability often evolves non-monotonically across iterations (see Figure 2 for Recycling and Adversarial Tiger). This finding is consistent with observations reported in (Delage et al., [7 ] ). CPI instead performs more expensive local updates based on explicit continuation
evaluations. This generally produces smoother exploitability profiles in the reported experiments (see Figure 2 ). A practical difference concerns exploitability evaluation. For CFR, exploitability must be estimated through an additional evaluation procedure whose cost increases with horizon. For fairness, these evaluation costs are included in the reported runtimes (see Table 1 ). Runtimes excluding the measurement cost are reported in Table 4 . In CPI, the quantities required to estimate deviations are maintained during policy improvement steps via the fixed-policy value function. So exploitability estimates are obtained directly from the algorithm. For larger horizons, exploitability estimates in CFR also become increasingly noisy, which can make convergence trends more difficult to interpret empirically. CFR+ remains attractive because of its inexpensive iterations, whereas CPI performs fewer but more costly updates. The two approaches therefore reflect different computational trade-offs between update cost and exploitability estimation.
Table 4. Snapshot of empirical results. For each game, horizon and algorithm, we report time, value and exploitability ϵ \epsilon ϵ associated with the computed ϵ \epsilon ϵ -Nash equilibrium. OOT occurs when the target exploitability threshold cannot be reached within the prescribed time limit, while OOM means that the algorithms ran out of memory. magenta = lowest exploitability value per benchmark, while ‘−’ means the time budget for computing the exploitability has been exceeded.
Takehome message. CFR+ benefits from inexpensive iterations, but typically requires more iterations and repeated exploitability evaluations to reach solution quality comparable to CPI. In our experiments, this often resulted in higher overall runtime at larger horizons. CPI instead performs fewer but more expensive updates, leading to a different trade-off between update cost, exploitability estimation, and empirical stability.
Conclusion
We introduced an approximate policy-iteration algorithm for finite-horizon zs-POSGs. The method combines elements from point-based value iteration and policy-search approaches. It maintains one policy per player and updates both policies along occupancy trajectories induced by conservative policy updates. Instead of approximating a global central value function, each update relies on a fixed-policy continuation value function associated with the current joint policy. The algorithm combines local policy improvements, conservative updates, and persistent exploration. The empirical results show that this approach is competitive on standard finite-horizon zs-POSG benchmarks. In several instances and horizons, it improves the runtime–exploitability trade-off compared with PBVI, HSVI, and CFR+.
Several limitations remain. First, the algorithm requires solving local optimisation problems for both players throughout training. Second, convergence can remain slow and the sample complexity high, which may limit scalability at larger horizons. Third, the current implementation still relies on linear programming subroutines, which may become computationally demanding in larger games. Future work will investigate iterative approximations of these optimisation steps, improved exploration and scheduling mechanisms, and neural approximations of the continuation value functions.
AI use statement
In this work, we used generative AI tools to assist with translation, provide critical ingredients for proving mathematical claims, assist in the development and refinement of mathematical proofs, edit the manuscript to improve readability, create and modify scientific figures, create and edit software code, summarize and analyze existing literature, and assist with sourcing and searching for relevant information.
We did not use generative AI tools to develop theoretical models or conceptual frameworks, formulate mathematical claims, propose or refine hypotheses, design research methodology or experiments, provide feedback on research methodology or experiments, implement the methods underlying the research, or interpret the results. The remaining categories of required disclosure are not applicable to this work.
All AI-assisted content and outputs were reviewed by the authors. The authors take full responsibility for the final content of this work, including all text, mathematical claims, proofs, figures, code, and other artifacts produced with the assistance of generative AI.
Proofs
Lemma 1. In a finite-horizon finite model, all behavioural-policy spaces are compact, and all payoff maps are continuous.
Proof. Each Π t i \Pi_t^i Π t i is a finite product of finite-dimensional simplexes. Each Π i \Pi^i Π i and each Π t : T \Pi_{t:T} Π t : T is a finite product of decision-rule spaces. Finite products of compact sets are compact. Every finite-horizon payoff is a finite sum of multilinear functions of behavioural-policy coordinates. Hence every finite-horizon payoff map is continuous. The extreme-value theorem gives attainment for every optimisation over these spaces.
Conditional kernels
If a conditioning event has zero probability, τ i , t c : C t i × Π t i × A − i × Z 0 × Z − i → C t + 1 i \tau_{i,t}^c:C_t^i\times\Pi_t^i\times A^{-i}\times Z^0\times Z^{-i}\to C_{t+1}^i τ i , t c : C t i × Π t i × A − i × Z 0 × Z − i → C t + 1 i is assigned an arbitrary fixed element of C t + 1 i C_{t+1}^i C t + 1 i . All such terms are multiplied by their zero likelihood.
Lemma 2. τ i , t c \tau_{i,t}^c τ i , t c is the Bayes update of ( S t + 1 , H t + 1 i ) (S_{t+1},H_{t+1}^i) ( S t + 1 , H t + 1 i ) given ( Z t + 1 0 , Z t + 1 − i ) (Z_{t+1}^0,Z_{t+1}^{-i}) ( Z t + 1 0 , Z t + 1 − i ) .
Proof. Fix ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) (c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^0,z_{t+1}^{-i}) ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) .
For ( s t + 1 , h t + 1 i ) (s_{t+1},h_{t+1}^i) ( s t + 1 , h t + 1 i ) , define
m ( s t + 1 , h t + 1 i ) ≔ ∑ s t , h t i , a t i , z t + 1 i c t i ( s t , h t i ) π t i ( a t i ∣ h t i ) ⋅ p ( s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i ∣ s t , a t i , a t − i ) ⋅ 1 { h t + 1 i = ( h t i , a t i , z t + 1 i ) } . m(s_{t+1},h_{t+1}^i)\coloneqq\sum_{s_t,h_t^i,a_t^i,z_{t+1}^i}c_t^i(s_t,h_t^i)\pi_t^i(a_t^i\mid h_t^i)
\cdot p(s_{t+1},z_{t+1}^0,z_{t+1}^i,z_{t+1}^{-i}\mid s_t,a_t^i,a_t^{-i})\cdot\mathbf{1}\{h_{t+1}^i=(h_t^i,a_t^i,z_{t+1}^i)\}. m ( s t + 1 , h t + 1 i ) : = s t , h t i , a t i , z t + 1 i ∑ c t i ( s t , h t i ) π t i ( a t i ∣ h t i ) ⋅ p ( s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i ∣ s t , a t i , a t − i ) ⋅ 1 { h t + 1 i = ( h t i , a t i , z t + 1 i )} .
Let W ≔ ∑ s t + 1 , h t + 1 i m ( s t + 1 , h t + 1 i ) W\coloneqq\sum_{s_{t+1},h_{t+1}^i}m(s_{t+1},h_{t+1}^i) W : = ∑ s t + 1 , h t + 1 i m ( s t + 1 , h t + 1 i ) .
If W > 0 W>0 W > 0 , then
τ i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) ( s t + 1 , h t + 1 i ) = m ( s t + 1 , h t + 1 i ) W . \tau_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^0,z_{t+1}^{-i})(s_{t+1},h_{t+1}^i)=\frac{m(s_{t+1},h_{t+1}^i)}{W}. τ i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) ( s t + 1 , h t + 1 i ) = W m ( s t + 1 , h t + 1 i ) .
If W = 0 W=0 W = 0 , every weighted term involving this update is zero.
Lemma 3. w i , t c : C t i × Π t i × A − i → Δ ( Z 0 × Z − i ) w_{i,t}^c:C_t^i\times\Pi_t^i\times A^{-i}\to\Delta(Z^0\times Z^{-i}) w i , t c : C t i × Π t i × A − i → Δ ( Z 0 × Z − i ) is a probability law over Z 0 × Z − i Z^0\times Z^{-i} Z 0 × Z − i .
Proof. Fix ( c t i , π t i , a t − i ) (c_t^i,\pi_t^i,a_t^{-i}) ( c t i , π t i , a t − i ) .
With m m m as in Lemma 2, define
w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) ≔ ∑ s t + 1 , h t + 1 i m ( s t + 1 , h t + 1 i ) . w_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^0,z_{t+1}^{-i})\coloneqq\sum_{s_{t+1},h_{t+1}^i}m(s_{t+1},h_{t+1}^i). w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) : = s t + 1 , h t + 1 i ∑ m ( s t + 1 , h t + 1 i ) .
Then w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) ≥ 0 w_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^0,z_{t+1}^{-i})\ge0 w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) ≥ 0 , and
∑ z t + 1 0 , z t + 1 − i w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) = ∑ s t , h t i c t i ( s t , h t i ) ∑ a t i π t i ( a t i ∣ h t i ) ⋅ ∑ s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i p ( s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i ∣ s t , a t i , a t − i ) = ∑ s t , h t i c t i ( s t , h t i ) ∑ a t i π t i ( a t i ∣ h t i ) = 1. \begin{aligned}
\sum_{z_{t+1}^0,z_{t+1}^{-i}}w_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^0,z_{t+1}^{-i})
&=\sum_{s_t,h_t^i}c_t^i(s_t,h_t^i)\sum_{a_t^i}\pi_t^i(a_t^i\mid h_t^i)\\
&\quad\cdot\sum_{s_{t+1},z_{t+1}^0,z_{t+1}^i,z_{t+1}^{-i}}p(s_{t+1},z_{t+1}^0,z_{t+1}^i,z_{t+1}^{-i}\mid s_t,a_t^i,a_t^{-i})\\
&=\sum_{s_t,h_t^i}c_t^i(s_t,h_t^i)\sum_{a_t^i}\pi_t^i(a_t^i\mid h_t^i)=1.
\end{aligned} z t + 1 0 , z t + 1 − i ∑ w i , t c ( c t i , π t i , a t − i , z t + 1 0 , z t + 1 − i ) = s t , h t i ∑ c t i ( s t , h t i ) a t i ∑ π t i ( a t i ∣ h t i ) ⋅ s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i ∑ p ( s t + 1 , z t + 1 0 , z t + 1 i , z t + 1 − i ∣ s t , a t i , a t − i ) = s t , h t i ∑ c t i ( s t , h t i ) a t i ∑ π t i ( a t i ∣ h t i ) = 1.
Lemma 4. g i , t c : C t i × Π t i × A − i → R g_{i,t}^c:C_t^i\times\Pi_t^i\times A^{-i}\to\mathbb{R} g i , t c : C t i × Π t i × A − i → R is the conditional expectation of r i ( S t , A t i , a t − i ) r^i(S_t,A_t^i,a_t^{-i}) r i ( S t , A t i , a t − i ) .
Proof. Fix ( c t i , π t i , a t − i ) (c_t^i,\pi_t^i,a_t^{-i}) ( c t i , π t i , a t − i ) .
E [ r i ( S t , A t i , a t − i ) ∣ c t i , π t i , a t − i ] = ∑ s t , h t c t i ( s t , h t ) ∑ a t i π t i ( a t i ∣ h t ) r i ( s t , a t i , a t − i ) = g i , t c ( c t i , π t i , a t − i ) . \mathbb{E}[r^i(S_t,A_t^i,a_t^{-i}) \mid c_t^i,\pi_t^i,a_t^{-i}]
= \sum_{s_t,h_t} c_t^i(s_t,h_t)\sum_{a_t^i}\pi_t^i(a_t^i\mid h_t)r^i(s_t,a_t^i,a_t^{-i})
= g_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i}). E [ r i ( S t , A t i , a t − i ) ∣ c t i , π t i , a t − i ] = s t , h t ∑ c t i ( s t , h t ) a t i ∑ π t i ( a t i ∣ h t ) r i ( s t , a t i , a t − i ) = g i , t c ( c t i , π t i , a t − i ) .
□ \square □
Lemma 5. p i , t c : C t i × Π t i × A − i → Δ ( C t + 1 i ) p_{i,t}^c:C_t^i\times\Pi_t^i\times A^{-i}\to\Delta(C_{t+1}^i) p i , t c : C t i × Π t i × A − i → Δ ( C t + 1 i ) is the pushforward of w i , t c w_{i,t}^c w i , t c by τ i , t c \tau_{i,t}^c τ i , t c .
Proof. Fix ( c t i , π t i , a t − i ) (c_t^i,\pi_t^i,a_t^{-i}) ( c t i , π t i , a t − i ) . For every c t + 1 i ∈ C t + 1 i c_{t+1}^i\in C_{t+1}^i c t + 1 i ∈ C t + 1 i ,
P ( C t + 1 i = c t + 1 i ∣ c t i , π t i , a t − i ) = ∑ z t + 1 i , z t + 1 − i w i , t c ( c t i , π t i , a t − i , z t + 1 i , z t + 1 − i ) ⋅ 1 { c t + 1 i = τ i , t c ( c t i , π t i , a t − i , z t + 1 i , z t + 1 − i ) } = p i , t c ( c t + 1 i ∣ c t i , π t i , a t − i ) . \mathbb{P}(C_{t+1}^i=c_{t+1}^i\mid c_t^i,\pi_t^i,a_t^{-i})
= \sum_{z_{t+1}^i,z_{t+1}^{-i}} w_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^i,z_{t+1}^{-i})\cdot\mathbf{1}\{c_{t+1}^i=\tau_{i,t}^c(c_t^i,\pi_t^i,a_t^{-i},z_{t+1}^i,z_{t+1}^{-i})\}
= p_{i,t}^c(c_{t+1}^i\mid c_t^i,\pi_t^i,a_t^{-i}). P ( C t + 1 i = c t + 1 i ∣ c t i , π t i , a t − i ) = z t + 1 i , z t + 1 − i ∑ w i , t c ( c t i , π t i , a t − i , z t + 1 i , z t + 1 − i ) ⋅ 1 { c t + 1 i = τ i , t c ( c t i , π t i , a t − i , z t + 1 i , z t + 1 − i )} = p i , t c ( c t + 1 i ∣ c t i , π t i , a t − i ) .
□ \square □
For fixed π t : T i \pi_{t:T}^i π t : T i , the recursion below defines v i , k π t : T i : C k i → R v_{i,k}^{\pi_{t:T}^i}:C_k^i\to\mathbb{R} v i , k π t : T i : C k i → R on C k i C_k^i C k i for every k ∈ { t , … , T } k\in\{t,\ldots,T\} k ∈ { t , … , T } . Define
v i , k π t : T i : c k i ↦ min π t : T − i E c k i , π t : T i [ ∑ κ = k T − 1 r i ( S κ , A κ i , A κ − i ) ] . v_{i,k}^{\pi_{t:T}^i}:c_k^i\mapsto\min_{\pi_{t:T}^{-i}}\mathbb{E}_{c_k^i,\pi_{t:T}^i}\left[\sum_{\kappa=k}^{T-1}r^i(S_\kappa,A_\kappa^i,A_\kappa^{-i})\right]. v i , k π t : T i : c k i ↦ π t : T − i min E c k i , π t : T i [ κ = k ∑ T − 1 r i ( S κ , A κ i , A κ − i ) ] .
Theorem 3. For fixed π t : T i \pi_{t:T}^i π t : T i , v i , k π t : T i v_{i,k}^{\pi_{t:T}^i} v i , k π t : T i satisfies the conditional Bellman recursion for every k ≥ t k\ge t k ≥ t .
Proof. At k = T k=T k = T , set v i , T π t : T i ≡ 0 v_{i,T}^{\pi_{t:T}^i}\equiv0 v i , T π t : T i ≡ 0 .
Fix k < T k<T k < T , c k i ∈ C k i c_k^i\in C_k^i c k i ∈ C k i , and the rule π k i \pi_k^i π k i induced by π t : T i \pi_{t:T}^i π t : T i .
For every a k − i ∈ A − i a_k^{-i}\in A^{-i} a k − i ∈ A − i , Lemmas 4 and 5 give
E [ r i ( S k , A k i , a k − i ) + v i , k + 1 π t : T i ( C k + 1 i ) ∣ c k i , π k i , a k − i ] = g i , k c ( c k i , π k i , a k − i ) + ∑ c k + 1 i ∈ supp ( p i , k c ( ⋅ ∣ c k i , π k i , a k − i ) ) p i , k c ( c k + 1 i ∣ c k i , π k i , a k − i ) v i , k + 1 π t : T i ( c k + 1 i ) . \mathbb{E}[r^i(S_k,A_k^i,a_k^{-i})+v_{i,k+1}^{\pi_{t:T}^i}(C_{k+1}^i)\mid c_k^i,\pi_k^i,a_k^{-i}]
= g_{i,k}^c(c_k^i,\pi_k^i,a_k^{-i})+
\sum_{c_{k+1}^i\in\operatorname{supp}(p_{i,k}^c(\cdot\mid c_k^i,\pi_k^i,a_k^{-i}))}
p_{i,k}^c(c_{k+1}^i\mid c_k^i,\pi_k^i,a_k^{-i})v_{i,k+1}^{\pi_{t:T}^i}(c_{k+1}^i). E [ r i ( S k , A k i , a k − i ) + v i , k + 1 π t : T i ( C k + 1 i ) ∣ c k i , π k i , a k − i ] = g i , k c ( c k i , π k i , a k − i ) + c k + 1 i ∈ supp ( p i , k c ( ⋅ ∣ c k i , π k i , a k − i )) ∑ p i , k c ( c k + 1 i ∣ c k i , π k i , a k − i ) v i , k + 1 π t : T i ( c k + 1 i ) .
Taking min a k − i ∈ A − i \min_{a_k^{-i}\in A^{-i}} min a k − i ∈ A − i gives the recursion. □ \square □
Belief dynamics
Define g t i : ( b t i , π t ) ↦ E b t i , π t [ r i ( S t , A t ) ] g_t^i:(b_t^i,\pi_t)\mapsto\mathbb{E}_{b_t^i,\pi_t}[r^i(S_t,A_t)] g t i : ( b t i , π t ) ↦ E b t i , π t [ r i ( S t , A t )] .
Lemma 6. g t i g_t^i g t i is the expectation of g i , t c g_{i,t}^c g i , t c under b b b .
Proof. Fix b ∈ B t i b\in B_t^i b ∈ B t i and π t = ( π t i , π t − i ) \pi_t=(\pi_t^i,\pi_t^{-i}) π t = ( π t i , π t − i ) .
By definition,
g t i ( b , π t ) = E b t i , π t [ r i ( S t , A t ) ] = E b t i , π t [ E C t i , π t i , π t − i ( C t i ) [ r i ( S t , A t ) ] ] = ∑ c t i ∈ C t i b ( c t i ) g i , t c ( c t i , π t i , π t − i ( c t i ) ) . g_t^i(b,\pi_t)=\mathbb{E}_{b_t^i,\pi_t}[r^i(S_t,A_t)]
=\mathbb{E}_{b_t^i,\pi_t}\left[\mathbb{E}_{C_t^i,\pi_t^i,\pi_t^{-i}(C_t^i)}[r^i(S_t,A_t)]\right]
=\sum_{c_t^i\in C_t^i}b(c_t^i)g_{i,t}^c(c_t^i,\pi_t^i,\pi_t^{-i}(c_t^i)). g t i ( b , π t ) = E b t i , π t [ r i ( S t , A t )] = E b t i , π t [ E C t i , π t i , π t − i ( C t i ) [ r i ( S t , A t )] ] = c t i ∈ C t i ∑ b ( c t i ) g i , t c ( c t i , π t i , π t − i ( c t i )) .
□ \square □
Lemma 7. τ t i \tau_t^i τ t i is the law of C t + 1 i C_{t+1}^i C t + 1 i under ( b , π t ) (b,\pi_t) ( b , π t ) . Proof. Fix b ∈ B t i b \in\mathcal{B}^{i}_{t} b ∈ B t i and π t = ( π t i , π t − i ) \pi_{t}=(\pi^{i}_{t},\pi^{-i}_{t}) π t = ( π t i , π t − i ) .
For every c t + 1 i ∈ C t + 1 i c^{i}_{t+1}\in\mathcal{C}^{i}_{t+1} c t + 1 i ∈ C t + 1 i ,
P b , π t ( c t + 1 i = c t + 1 i ) = ∑ c t i ∈ C t i b ( c t i ) p t i ( c t + 1 i ∣ c t i , π t i , π t − i ( c t i ) ) = τ t i ( b , π t ) ( c t + 1 i ) . \mathbb{P}_{b,\pi_{t}}(c^{i}_{t+1} = c^{i}_{t+1}) = \sum_{c^{i}_{t}\in\mathcal{C}^{i}_{t}} b(c^{i}_{t})p^{i}_{t}(c^{i}_{t+1}\mid c^{i}_{t},\pi^{i}_{t},\pi^{-i}_{t}(c^{i}_{t})) = \tau^{i}_{t}(b,\pi_{t})(c^{i}_{t+1}). P b , π t ( c t + 1 i = c t + 1 i ) = c t i ∈ C t i ∑ b ( c t i ) p t i ( c t + 1 i ∣ c t i , π t i , π t − i ( c t i )) = τ t i ( b , π t ) ( c t + 1 i ) .
Lemma 8. For separable payoffs , the minimisation over π t − i \pi^{-i}_{t} π t − i decomposes pointwise.
Proof. Let F : C t i × A − i → R F:\mathcal{C}^{i}_{t}\times\mathcal{A}^{-i}\to\mathbb{R} F : C t i × A − i → R .
For every π t − i \pi^{-i}_{t} π t − i ,
∑ c t i b ( c t i ) F ( c t i , π t − i ( c t i ) ) ≥ ∑ c t i b ( c t i ) min a t − i F ( c t i , a t − i ) . \sum_{c^{i}_{t}} b(c^{i}_{t})F(c^{i}_{t},\pi^{-i}_{t}(c^{i}_{t}))\geq\sum_{c^{i}_{t}}b(c^{i}_{t})\min_{a^{-i}_{t}}F(c^{i}_{t},a^{-i}_{t}). c t i ∑ b ( c t i ) F ( c t i , π t − i ( c t i )) ≥ c t i ∑ b ( c t i ) a t − i min F ( c t i , a t − i ) . Choose
π t , ∗ − i ( c t i ) ∈ arg min a t − i ∈ A − i F ( c t i , a t − i ) . \pi^{-i}_{t,*}(c^{i}_{t})\in\underset{a^{-i}_{t}\in\mathcal{A}^{-i}}{\arg\min}\ F(c^{i}_{t},a^{-i}_{t}). π t , ∗ − i ( c t i ) ∈ a t − i ∈ A − i arg min F ( c t i , a t − i ) . Then
∑ c t i b ( c t i ) F ( c t i , π t , ∗ − i ( c t i ) ) = ∑ c t i b ( c t i ) min a t − i F ( c t i , a t − i ) . \sum_{c^{i}_{t}}b(c^{i}_{t})F(c^{i}_{t},\pi^{-i}_{t,*}(c^{i}_{t}))=\sum_{c^{i}_{t}}b(c^{i}_{t})\min_{a^{-i}_{t}}F(c^{i}_{t},a^{-i}_{t}). c t i ∑ b ( c t i ) F ( c t i , π t , ∗ − i ( c t i )) = c t i ∑ b ( c t i ) a t − i min F ( c t i , a t − i ) .
Continuation values
Define
v i , t c o n t ( b ) ≔ max π t : T i min π t : T − i E b , π t : T i , π t : T − i [ ∑ k = t T − 1 r i ( S k , A k ) ] . v^{\mathrm{cont}}_{i,t}(b)\coloneqq\max_{\pi^{i}_{t:T}}\min_{\pi^{-i}_{t:T}}\mathbb{E}_{b,\pi^{i}_{t:T},\pi^{-i}_{t:T}}\left[\sum_{k=t}^{T-1}r^{i}(S_{k},A_{k})\right]. v i , t cont ( b ) : = π t : T i max π t : T − i min E b , π t : T i , π t : T − i [ k = t ∑ T − 1 r i ( S k , A k ) ] .
Lemma 9. v i , t c o n t v^{\mathrm{cont}}_{i,t} v i , t cont satisfies the focal belief Bellman recursion.
Proof. At t = T t=T t = T , v i , T c o n t = 0 v^{\mathrm{cont}}_{i,T}=0 v i , T cont = 0 .
Fix t < T t<T t < T . Rearranging max and min operators require replacing opponent deterministic policy suffix π t − i \pi^{-i}_{t} π t − i by a mixed one. For any ( π t i , π t − i ) (\pi^{i}_{t},\pi^{-i}_{t}) ( π t i , π t − i ) , Lemmas 6 and 7 give
E b , π t , π t + 1 : T i , π t + 1 : T − i [ ∑ k = t T − 1 r i ( S k , A k ) ] = g t i ( b , π t ) + E τ t i ( b , π t ) , π t + 1 : T i , π t + 1 : T − i [ ∑ k = t + 1 T − 1 r i ( S k , A k ) ] . \mathbb{E}_{b,\pi_{t},\pi^{i}_{t+1:T},\pi^{-i}_{t+1:T}}\left[\sum_{k=t}^{T-1}r^{i}(S_{k},A_{k})\right]
=g^{i}_{t}(b,\pi_{t})+\mathbb{E}_{\tau^{i}_{t}(b,\pi_{t}),\pi^{i}_{t+1:T},\pi^{-i}_{t+1:T}}\left[\sum_{k=t+1}^{T-1}r^{i}(S_{k},A_{k})\right]. E b , π t , π t + 1 : T i , π t + 1 : T − i [ k = t ∑ T − 1 r i ( S k , A k ) ] = g t i ( b , π t ) + E τ t i ( b , π t ) , π t + 1 : T i , π t + 1 : T − i [ k = t + 1 ∑ T − 1 r i ( S k , A k ) ] . Decomposing the policy space and optimising gives
v i , t c o n t ( b ) = max π t i min π t − i [ g t i ( b , π t ) + v i , t + 1 c o n t ( τ t i ( b , π t ) ) ] . v^{\mathrm{cont}}_{i,t}(b)=\max_{\pi^{i}_{t}}\min_{\pi^{-i}_{t}}\left[g^{i}_{t}(b,\pi_{t})+v^{\mathrm{cont}}_{i,t+1}\left(\tau^{i}_{t}(b,\pi_{t})\right)\right]. v i , t cont ( b ) = π t i max π t − i min [ g t i ( b , π t ) + v i , t + 1 cont ( τ t i ( b , π t ) ) ] . where the interchange of max and min is established using arguments similar to those in Delage et al. [7 ] and Escudie et al. [14 ] .
Theorem 4. The optimal focal belief value function v t i , ∗ v^{i,*}_{t} v t i , ∗ satisfies the focal belief Bellman equation and equals v i , t c o n t v^{\mathrm{cont}}_{i,t} v i , t cont .
Proof. Both functions have terminal value zero. Assume v t + 1 i , ∗ = v i , t + 1 c o n t v^{i,*}_{t+1}=v^{\mathrm{cont}}_{i,t+1} v t + 1 i , ∗ = v i , t + 1 cont . By Lemma 9,
v i , t c o n t ( b ) = max π t i min π t − i [ g t i ( b , π t ) + v t + 1 i , ∗ ( τ t i ( b , π t ) ) ] . v^{\mathrm{cont}}_{i,t}(b)=\max_{\pi_t^i}\min_{\pi_t^{-i}}\left[g_t^i(b,\pi_t)+v^{i,*}_{t+1}\left(\tau_t^i(b,\pi_t)\right)\right]. v i , t cont ( b ) = π t i max π t − i min [ g t i ( b , π t ) + v t + 1 i , ∗ ( τ t i ( b , π t ) ) ] .
The right-hand side is the Bellman definition of v t i , ∗ ( b ) v^{i,*}_t(b) v t i , ∗ ( b ) . Backward induction gives the claim.
Focal decomposition
Lemma 10. A prefix pair ( π 0 : t i , π 0 : t − i ) (\pi^i_{0:t},\pi^{-i}_{0:t}) ( π 0 : t i , π 0 : t − i ) induces b k + 1 i = τ k i ( b k i , π k ) b^i_{k+1}=\tau^i_k(b^i_k,\pi_k) b k + 1 i = τ k i ( b k i , π k ) .
Proof. At k = 0 k=0 k = 0 , b 0 i b^i_0 b 0 i is induced by b 0 b_0 b 0 . If b k i b^i_k b k i is the law of C k i C^i_k C k i , then Lemma 7 gives
b k + 1 i = τ k i ( b k i , π k ) . b^i_{k+1}=\tau^i_k(b^i_k,\pi_k). b k + 1 i = τ k i ( b k i , π k ) .
Proof of Theorem 1
For fixed π t : T i \pi^i_{t:T} π t : T i , define
v i , k π t : T i ( b ) = min π k : T i E b , π k : T i , π k : T − i [ ∑ ℓ = k T − 1 r i ( S ℓ , A ℓ ) ] . v^{\pi^i_{t:T}}_{i,k}(b)=\min_{\pi^i_{k:T}}\mathbb{E}_{b,\pi^i_{k:T},\pi^{-i}_{k:T}}\left[\sum_{\ell=k}^{T-1}r^i(S_\ell,A_\ell)\right]. v i , k π t : T i ( b ) = π k : T i min E b , π k : T i , π k : T − i [ ℓ = k ∑ T − 1 r i ( S ℓ , A ℓ ) ] .
where π k : T i \pi^i_{k:T} π k : T i is the tail of π t : T i \pi^i_{t:T} π t : T i .
Lemma 11. For fixed π t : T i \pi^i_{t:T} π t : T i and k ≥ t k\ge t k ≥ t , v i , k π t : T i v^{\pi^i_{t:T}}_{i,k} v i , k π t : T i is linear on B k i B^i_k B k i .
Proof. For c ∈ C k i c\in C^i_k c ∈ C k i , set
w i , k π t : T i ( c ) = v i , k π t : T i ( c ) . w^{\pi^i_{t:T}}_{i,k}(c)=v^{\pi^i_{t:T}}_{i,k}(c). w i , k π t : T i ( c ) = v i , k π t : T i ( c ) .
We prove by backward induction that
v i , k π t : T i ( b ) = ∑ c ∈ C k i b ( c ) w i , k π t : T i ( c ) . v^{\pi^i_{t:T}}_{i,k}(b)=\sum_{c\in C^i_k}b(c)w^{\pi^i_{t:T}}_{i,k}(c). v i , k π t : T i ( b ) = c ∈ C k i ∑ b ( c ) w i , k π t : T i ( c ) .
The claim is zero at k = T k=T k = T .
Assume it holds at k + 1 k+1 k + 1 . The stage-k k k focal rule π k i \pi^i_k π k i is fixed. By Lemmas 6, 7, and the induction hypothesis,
v i , k π t : T i ( b ) = min π k i ∑ c ∈ C k i b ( c ) [ g i , k c ( c , π k i , π k − i ( c ) ) + ∑ c ′ ∈ C k + 1 i p i , k c ( c ′ ∣ c , π k i , π k − i ( c ) ) w i , k + 1 π t : T i ( c ′ ) ] . \begin{aligned}
v^{\pi^i_{t:T}}_{i,k}(b)
&=\min_{\pi^i_k}\sum_{c\in C^i_k}b(c)\left[g^c_{i,k}(c,\pi^i_k,\pi^{-i}_k(c))\right.\\
&\qquad\left.+\sum_{c'\in C^i_{k+1}}p^c_{i,k}(c'\mid c,\pi^i_k,\pi^{-i}_k(c))w^{\pi^i_{t:T}}_{i,k+1}(c')\right].
\end{aligned} v i , k π t : T i ( b ) = π k i min c ∈ C k i ∑ b ( c ) [ g i , k c ( c , π k i , π k − i ( c )) + c ′ ∈ C k + 1 i ∑ p i , k c ( c ′ ∣ c , π k i , π k − i ( c )) w i , k + 1 π t : T i ( c ′ ) .
By Lemma 8,
v i , k π t : T i ( b ) = ∑ c ∈ C k i b ( c ) min a − i [ g i , k c ( c , π k i , a − i ) + ∑ c ′ ∈ C k + 1 i p i , k c ( c ′ ∣ c , π k i , a − i ) w i , k + 1 π t : T i ( c ′ ) ] . \begin{aligned}
v^{\pi^i_{t:T}}_{i,k}(b)
&=\sum_{c\in C^i_k}b(c)\min_{a^{-i}}\left[g^c_{i,k}(c,\pi^i_k,a^{-i})\right.\\
&\qquad\left.+\sum_{c'\in C^i_{k+1}}p^c_{i,k}(c'\mid c,\pi^i_k,a^{-i})w^{\pi^i_{t:T}}_{i,k+1}(c')\right].
\end{aligned} v i , k π t : T i ( b ) = c ∈ C k i ∑ b ( c ) a − i min [ g i , k c ( c , π k i , a − i ) + c ′ ∈ C k + 1 i ∑ p i , k c ( c ′ ∣ c , π k i , a − i ) w i , k + 1 π t : T i ( c ′ ) .
By Theorem 3, the inner minimum equals w i , k π t : T i ( c ) w^{\pi^i_{t:T}}_{i,k}(c) w i , k π t : T i ( c ) . Thus
v i , k π t : T i ( b ) = ∑ c ∈ C k i b ( c ) w i , k π t : T i ( c ) . v^{\pi^i_{t:T}}_{i,k}(b)=\sum_{c\in C^i_k}b(c)w^{\pi^i_{t:T}}_{i,k}(c). v i , k π t : T i ( b ) = c ∈ C k i ∑ b ( c ) w i , k π t : T i ( c ) .
Linearity follows.
Theorem 5. v t i , ∗ v_t^{i,*} v t i , ∗ is convex, and v t i , ∗ ( b ) = max v ∈ Γ i , t v ( b ) v_t^{i,*}(b)=\max_{v\in\Gamma_{i,t}}v(b) v t i , ∗ ( b ) = max v ∈ Γ i , t v ( b ) for all b ∈ B t i b\in\mathcal{B}_t^i b ∈ B t i .
Proof. Let
Γ i , t ≔ { v i , t π t : T i : π t : T i ∈ Π t : T } . \Gamma_{i,t} \coloneqq\{v_{i,t}^{\pi_{t:T}^i}:\pi_{t:T}^i\in\Pi_{t:T}\}. Γ i , t : = { v i , t π t : T i : π t : T i ∈ Π t : T } . By Lemma 1, Γ i , t \Gamma_{i,t} Γ i , t is compact in the finite-dimensional space of linear functionals.
By Theorem 4,
v t i , ∗ ( b ) = v i , t c o n t ( b ) . v_t^{i,*}(b)=v_{i,t}^{\mathrm{cont}}(b). v t i , ∗ ( b ) = v i , t cont ( b ) . By definition of v i , t c o n t v_{i,t}^{\mathrm{cont}} v i , t cont ,
v i , t c o n t ( b ) = max π t : T i ∈ Π t : T v i , t π t : T i ( b ) . v_{i,t}^{\mathrm{cont}}(b)=\max_{\pi_{t:T}^i\in\Pi_{t:T}}v_{i,t}^{\pi_{t:T}^i}(b). v i , t cont ( b ) = π t : T i ∈ Π t : T max v i , t π t : T i ( b ) . Hence
v t i , ∗ ( b ) = max v ∈ Γ i , t v ( b ) . v_t^{i,*}(b)=\max_{v\in\Gamma_{i,t}}v(b). v t i , ∗ ( b ) = v ∈ Γ i , t max v ( b ) . For b , b ′ ∈ B t i b,b'\in\mathcal{B}_t^i b , b ′ ∈ B t i and λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] ,
v t i , ∗ ( λ b + ( 1 − λ ) b ′ ) = max v ∈ Γ i , t v ( λ b + ( 1 − λ ) b ′ ) = max v ∈ Γ i , t [ λ v ( b ) + ( 1 − λ ) v ( b ′ ) ] ≤ λ v t i , ∗ ( b ) + ( 1 − λ ) v t i , ∗ ( b ′ ) . \begin{aligned}
v_t^{i,*}(\lambda b+(1-\lambda)b')&=\max_{v\in\Gamma_{i,t}}v(\lambda b+(1-\lambda)b')\\
&=\max_{v\in\Gamma_{i,t}}[\lambda v(b)+(1-\lambda)v(b')]\\
&\leq\lambda v_t^{i,*}(b)+(1-\lambda)v_t^{i,*}(b').
\end{aligned} v t i , ∗ ( λb + ( 1 − λ ) b ′ ) = v ∈ Γ i , t max v ( λb + ( 1 − λ ) b ′ ) = v ∈ Γ i , t max [ λ v ( b ) + ( 1 − λ ) v ( b ′ )] ≤ λ v t i , ∗ ( b ) + ( 1 − λ ) v t i , ∗ ( b ′ ) . Thus v t i , ∗ v_t^{i,*} v t i , ∗ is convex.
Local Bellman backups
The theorem is conditional on finite coverage, Bellman closure, globally valid inserted vectors, infinite exact updates, and covered-backup consistency.
Local point-based backup
We introduce the following linear program to compute a greedy decision rule with respect to a fixed continuation policy π t + 1 : T i \pi_{t+1:T}^i π t + 1 : T i and focal belief b t i b_t^i b t i .
The program uses the following variables:
v ( c t i ) v(c_t^i) v ( c t i ) , representing the value associated with conditional state c t i c_t^i c t i ,
η ( h t + 1 − i , h t + 1 0 ) \eta(h_{t+1}^{-i},h_{t+1}^0) η ( h t + 1 − i , h t + 1 0 ) , representing auxiliary continuation values,
π t i ∈ Π t i \pi_t^i\in\Pi_t^i π t i ∈ Π t i , the focal decision rule to optimize.
Theorem 6. For any fixed suffix policy π t + 1 : T i \pi_{t+1:T}^i π t + 1 : T i (associated with its value function Λ i , t + 1 \Lambda_{i,t+1} Λ i , t + 1 ), and focal belief b t i ∈ B t i b_t^i\in\mathcal{B}_t^i b t i ∈ B t i , solving the linear program
M a x ∑ c t i b t i ( c t i ) v ( c t i ) S u b j e c t t o v ( c t i ) ≤ ∑ z t − i , z t 0 η ( h t + 1 − i , h t + 1 0 ) , ∀ c t i , a t − i η ( h t + 1 − i , h t + 1 0 ) ≤ ∑ h t i , a t i π t i ( a t i ∣ h t i , h t 0 ) Q ( h t + 1 − i , h t + 1 i , α ) , ∀ h t + 1 − i , h t + 1 0 , α ∈ Λ i , t + 1 , π t i ∈ Π t i \begin{aligned}
\mathop{\mathrm{Max}}\quad&\sum_{c_t^i}b_t^i(c_t^i)v(c_t^i)\\
\mathop{\mathrm{Subject\ to}}\quad&v(c_t^i)\leq\sum_{z_t^{-i},z_t^0}\eta(h_{t+1}^{-i},h_{t+1}^0),\qquad\forall c_t^i,a_t^{-i}\\
&\eta(h_{t+1}^{-i},h_{t+1}^0)\leq\sum_{h_t^i,a_t^i}\pi_t^i(a_t^i\mid h_t^i,h_t^0)Q_{(h_{t+1}^{-i},h_{t+1}^i,\alpha)},\\
&\hspace{7cm}\forall h_{t+1}^{-i},h_{t+1}^0,\alpha\in\Lambda_{i,t+1},\\
&\pi_t^i\in\Pi_t^i
\end{aligned} Max Subject to c t i ∑ b t i ( c t i ) v ( c t i ) v ( c t i ) ≤ z t − i , z t 0 ∑ η ( h t + 1 − i , h t + 1 0 ) , ∀ c t i , a t − i η ( h t + 1 − i , h t + 1 0 ) ≤ h t i , a t i ∑ π t i ( a t i ∣ h t i , h t 0 ) Q ( h t + 1 − i , h t + 1 i , α ) , ∀ h t + 1 − i , h t + 1 0 , α ∈ Λ i , t + 1 , π t i ∈ Π t i where
( h t + 1 − i , h t + 1 0 ) = ( c t i , a t − i , z t − i , z t 0 ) , (h_{t+1}^{-i},h_{t+1}^0)=(c_t^i,a_t^{-i},z_t^{-i},z_t^0), ( h t + 1 − i , h t + 1 0 ) = ( c t i , a t − i , z t − i , z t 0 ) , yields a decision rule π t i \pi_t^i π t i that greedily maximizes
q t π t + 1 : T i ( b t i , π t i ) = min π t − i [ g t i ( b t i , π t i , π t − i ) + v i , t + 1 π t + 1 : T i ( τ t i ( b t i , π t i , π t − i ) ) ] , q_{t}^{\pi_{t+1:T}^i}(b_t^i,\pi_t^i)=\min_{\pi_t^{-i}}\left[g_t^i(b_t^i,\pi_t^i,\pi_t^{-i})+v_{i,t+1}^{\pi_{t+1:T}^i}\left(\tau_t^i(b_t^i,\pi_t^i,\pi_t^{-i})\right)\right], q t π t + 1 : T i ( b t i , π t i ) = π t − i min [ g t i ( b t i , π t i , π t − i ) + v i , t + 1 π t + 1 : T i ( τ t i ( b t i , π t i , π t − i ) ) ] , corresponding to the Q Q Q -value induced by the fixed-policy continuation ( π t i , π t + 1 : T i ) (\pi_t^i,\pi_{t+1:T}^i) ( π t i , π t + 1 : T i ) .
Proof. By construction, q ˉ t + 1 : T π i \bar{q}^{\pi^i}_{t+1:T} q ˉ t + 1 : T π i is consistent with v t + 1 : T π i v^{\pi^i}_{t+1:T} v t + 1 : T π i , and an optimal π t − i \pi^{-i}_t π t − i can be taken deterministic (since the suffix policy π t + 1 : T i \pi^i_{t+1:T} π t + 1 : T i is fixed).
A greedy decision rule maximizes \bar{q}^{\pi^i}_{t+1:T}_t over reachable beliefs:
max π t i q ˉ t + 1 : T π i ( b t i , π t i ) = max π t i min π t − i [ g t i ( b t i , π t i , π t − i ) + v t + 1 : T π i ( τ t i ( b t i , π t i , π t − i ) ) ] = max π t i min π t − i [ g t i ( b t i , π t i , π t − i ) + ∑ c t + 1 i b t + 1 i ( c t + 1 i ) min α t + 1 : T π i α t + 1 : T π i ⋅ c t + 1 i ] , \begin{aligned}
\max_{\pi^i_t}\bar{q}^{\pi^i}_{t+1:T}(b^i_t,\pi^i_t)=\max_{\pi^i_t}\min_{\pi^{-i}_t}\left[g^i_t(b^i_t,\pi^i_t,\pi^{-i}_t)+v^{\pi^i}_{t+1:T}\left(\tau^i_t(b^i_t,\pi^i_t,\pi^{-i}_t)\right)\right] \\
&=\max_{\pi^i_t}\min_{\pi^{-i}_t}\left[g^i_t(b^i_t,\pi^i_t,\pi^{-i}_t)+\sum_{c^i_{t+1}}b^i_{t+1}(c^i_{t+1})\min_{\alpha^{\pi^i}_{t+1:T}}\alpha^{\pi^i}_{t+1:T}\cdot c^i_{t+1}\right],
\end{aligned} π t i max q ˉ t + 1 : T π i ( b t i , π t i ) = π t i max π t − i min [ g t i ( b t i , π t i , π t − i ) + v t + 1 : T π i ( τ t i ( b t i , π t i , π t − i ) ) ] = π t i max π t − i min g t i ( b t i , π t i , π t − i ) + c t + 1 i ∑ b t + 1 i ( c t + 1 i ) α t + 1 : T π i min α t + 1 : T π i ⋅ c t + 1 i ,
where b t + 1 i = τ t i ( b t i , π t i , π t − i ) b^i_{t+1}=\tau^i_t(b^i_t,\pi^i_t,\pi^{-i}_t) b t + 1 i = τ t i ( b t i , π t i , π t − i ) .
Expanding the belief update and rearranging terms, we obtain:
max π t i q ˉ t + 1 : T π i ( b t i , π t i ) = max π t i min π t − i ∑ h t − i , a t − i , z t − i , z t 0 π t − i ( a t − i ∣ h t − i , h t 0 ) ⋅ min α t + 1 : T π i ∑ h t i , a t i π t i ( a t i ∣ h t i , h t 0 ) ∑ s t b t i ( s t , h t ) ⋅ [ g t i ( s t , a t i , a t − i ) + ∑ s t + 1 , z t p ( s t + 1 , z t , z t 0 ∣ s t , a t ) α t + 1 : T π i ( c t + 1 i ) ] . \begin{aligned}
\max_{\pi^i_t}\bar{q}^{\pi^i}_{t+1:T}(b^i_t,\pi^i_t)=\max_{\pi^i_t}\min_{\pi^{-i}_t}\sum_{h^{-i}_t,a^{-i}_t,z^{-i}_t,z^0_t}\pi^{-i}_t(a^{-i}_t\mid h^{-i}_t,h^0_t) \\
&\cdot\min_{\alpha^{\pi^i}_{t+1:T}}\sum_{h^i_t,a^i_t}\pi^i_t(a^i_t\mid h^i_t,h^0_t)\sum_{s_t}b^i_t(s_t,h_t) \\
&\cdot\left[g^i_t(s_t,a^i_t,a^{-i}_t)+\sum_{s_{t+1},z_t}p(s_{t+1},z_t,z^0_t\mid s_t,a_t)\alpha^{\pi^i}_{t+1:T}(c^i_{t+1})\right].
\end{aligned} π t i max q ˉ t + 1 : T π i ( b t i , π t i ) = π t i max π t − i min h t − i , a t − i , z t − i , z t 0 ∑ π t − i ( a t − i ∣ h t − i , h t 0 ) ⋅ α t + 1 : T π i min h t i , a t i ∑ π t i ( a t i ∣ h t i , h t 0 ) s t ∑ b t i ( s t , h t ) ⋅ [ g t i ( s t , a t i , a t − i ) + s t + 1 , z t ∑ p ( s t + 1 , z t , z t 0 ∣ s t , a t ) α t + 1 : T π i ( c t + 1 i ) ] .
This expression makes explicit the max–min structure together with the inner minimization over α \alpha α , where α \alpha α is taken after the expectation over next-stage variables. This placement is crucial: it preserves the piecewise-linear concave structure of the value function and yields directly the desired linear programming formulation.
If we denote ( h t + 1 − i , h t + 1 0 ) = ( c t i , a t − i , z t − i , z t 0 ) (h^{-i}_{t+1},h^0_{t+1})=(c^i_t,a^{-i}_t,z^{-i}_t,z^0_t) ( h t + 1 − i , h t + 1 0 ) = ( c t i , a t − i , z t − i , z t 0 ) , using the bijection between c t i c^i_t c t i and the pair of histories ( h t − i , h t 0 ) (h^{-i}_t,h^0_t) ( h t − i , h t 0 ) , we can define
Q ( h t + 1 − i , h t + 1 i , α ) = ∑ s t b t i ( s t , h t ) [ g t i ( s t , a t i , a t − i ) + ∑ s t + 1 , z t p ( s t + 1 , z t , z t 0 ∣ s t , a t ) α t + 1 : T π i ( c t + 1 i ) ] , \begin{aligned}
Q_{(h^{-i}_{t+1},h^i_{t+1},\alpha)} \\
&=\sum_{s_t}b^i_t(s_t,h_t)\left[g^i_t(s_t,a^i_t,a^{-i}_t)+\sum_{s_{t+1},z_t}p(s_{t+1},z_t,z^0_t\mid s_t,a_t)\alpha^{\pi^i}_{t+1:T}(c^i_{t+1})\right],
\end{aligned} Q ( h t + 1 − i , h t + 1 i , α ) = s t ∑ b t i ( s t , h t ) [ g t i ( s t , a t i , a t − i ) + s t + 1 , z t ∑ p ( s t + 1 , z t , z t 0 ∣ s t , a t ) α t + 1 : T π i ( c t + 1 i ) ] ,
then the above quantity corresponds to the q q q -value of the best response where player − i -i − i plays a t − i a^{-i}_t a t − i in c t i c^i_t c t i and follows α t + 1 : T π i \alpha^{\pi^i}_{t+1:T} α t + 1 : T π i at ( h t + 1 − i , h t + 1 0 ) (h^{-i}_{t+1},h^0_{t+1}) ( h t + 1 − i , h t + 1 0 ) . This yields the coefficients of the linear program described in the theorem.
We also impose an additional constraint on π t i \pi^i_t π t i to ensure that it is a valid decision rule, i.e., that each local strategy belongs to the simplex:
π t i ( ⋅ ∣ h t i , h t 0 ) ∈ Δ ( A i ) , ∀ h t i , h t 0 \pi^i_t(\cdot\mid h^i_t,h^0_t)\in\Delta(\mathcal{A}^i),\quad\forall h^i_t,h^0_t π t i ( ⋅ ∣ h t i , h t 0 ) ∈ Δ ( A i ) , ∀ h t i , h t 0
ensuring that π t i \pi^i_t π t i defines a proper probability distribution over actions at every local history.
Comparative Analysis of Backup Complexity
Comparative analysis: Delage et al. [7 ] The OMG greedy-update formulation Delage et al. [7 ] enforces pessimism against all deterministic opponent decision rules π t − i : H t 2 → A t 2 \pi^{-i}_t:H^2_t\to A^2_t π t − i : H t 2 → A t 2 . Because there are ∣ A t 2 ∣ ∣ H t 2 ∣ |A^2_t|^{|H^2_t|} ∣ A t 2 ∣ ∣ H t 2 ∣ such mappings, the LP description contains O ( ∣ A t 2 ∣ ∣ H t 2 ∣ ) O(|A^2_t|^{|H^2_t|}) O ( ∣ A t 2 ∣ ∣ H t 2 ∣ ) constraints (Table 2), which is exponential in the size of the opponent’s private-history space. Our backup removes this bottleneck by never indexing constraints by opponent decision rules: our LP constrains only against finitely many vectors in a cached envelope Λ \Lambda Λ . Hence our LP admits polynomial-size descriptions in the explicit parameters ∣ H t 1 ∣ |H^1_t| ∣ H t 1 ∣ , ∣ H t 2 ∣ |H^2_t| ∣ H t 2 ∣ , ∣ A t 1 ∣ |A^1_t| ∣ A t 1 ∣ , ∣ A t 2 ∣ |A^2_t| ∣ A t 2 ∣ , ∣ Z t 2 ∣ |Z^2_t| ∣ Z t 2 ∣ , ∣ Λ ∣ |\Lambda| ∣Λ∣ .
Comparative analysis: Escudie et al. [14 ] In Escudie et al., [14 ] , the LP explicitly incorporates all candidate next policies of i i i through the sets Γ 1 \Gamma_1 Γ 1 of piecewise linear concave function Λ \Lambda Λ , which grow over iterations. Specifically, a single monolithic greedy LP jointly couples the outer cache index Γ 1 \Gamma_1 Γ 1 , the inner value index α ∈ Λ \alpha\in\Lambda α ∈ Λ , and the opponent action-observation indices ( a t 2 , z t 2 ) (a_t^2, z_t^2) ( a t 2 , z t 2 ) . This full coupling within a single program leads to a constraint count of O ( ∣ Γ 1 ∣ ⋅ ∣ Λ ∣ ⋅ ∣ H t 2 ∣ ⋅ ∣ A t 2 ∣ ⋅ ∣ Z t 2 ∣ ) O(|\Gamma_1|\cdot|\Lambda|\cdot|H_t^2|\cdot|A_t^2|\cdot|Z_t^2|) O ( ∣ Γ 1 ∣ ⋅ ∣Λ∣ ⋅ ∣ H t 2 ∣ ⋅ ∣ A t 2 ∣ ⋅ ∣ Z t 2 ∣ ) , as reported in Table 2 .
Table 2. LP complexity comparison (input-size view). The OMG greedy-update LP has constraints indexed by opponent decision rules, yielding an exponential dependence on ∣ H t 2 ∣ |H_t^2| ∣ H t 2 ∣ Delage et al., [7 ] . Both the cached-envelope greedy LP Escudie et al., [14 ] and our backup scale polynomially in the same explicit representation objects, but expose different optimization structures. In our formulation, both the number of variables and constraints are reduced by a factor of ∣ Γ 1 ∣ |\Gamma_1| ∣ Γ 1 ∣ . Here, ∣ Γ 1 ∣ |\Gamma_1| ∣ Γ 1 ∣ denotes the number of piecewise-linear concave functions maintained, while ∣ Λ ∣ |\Lambda| ∣Λ∣ is the number of piecewise-linear vectors associated with each element of Γ 1 \Gamma_1 Γ 1 .
Although the reduction in ∣ Γ 1 ∣ |\Gamma_1| ∣ Γ 1 ∣ has little impact for short horizons, it becomes critical for longer horizons. Indeed, in PBVI Escudie et al., [14 ] , the size of Γ 1 \Gamma_1 Γ 1 grows with the number of sampled points, which itself increases with the number of stages required to cover an ever-expanding continuous state space.
Algorithm
Value iteration in Escudie et al., [14 ] amounts to solving a focal belief game using sampled opponent behaviors. However, this unguided sampling process induces an exponential growth in the number of sampled points, resulting in a rapidly increasing computational complexity. To address this limitation, we introduce a policy iteration approach that exploits the structural properties of the game together with the reduced formulations defined previously. Leveraging this structure yields a more efficient iterative procedure while preserving optimality guarantees.
We prove that the dynamics induced by the game can be viewed as a discretization of a continuous-time dynamical system. Along the resulting continuous trajectory, the dual gap is non-increasing and converges to zero. The proof relies on three key properties: the convexity of the dual gap in the policy space, the differentiability of the value function almost everywhere, and the uniform continuity of the value function. Together, these properties allow us to characterize the evolution of the dual gap along the continuous dynamics and establish its convergence.
This section introduces and formally defines the main objects used throughout the analysis, including the dual gap and the dynamics guiding the update F t i F_t^i F t i , and related quantities.
The continuous dynamics describe the infinitesimal policy updates underlying the algorithm. At each stage t t t , the update acts on the policy π t i \pi_t^i π t i while the policies at other stages are kept fixed. The resulting direction therefore belongs to the local policy space Π t i \Pi_t^i Π t i , while depending on the complete policy of player i i i and the opponent’s policies up to stage t − 1 t-1 t − 1 through the induced belief state. This defines a vector field over the policy space, whose integral curves describe the continuous version of the algorithm.
Definition 4 (Continuous Dynamics). For player i i i and stage t t t , the continuous dynamics are defined as the vector field
F t i : Π 0 : T − 1 i × Π 0 : t − 1 − i → Π t i , F_t^i : \Pi_{0:T-1}^i \times\Pi_{0:t-1}^{-i} \to\Pi_t^i, F t i : Π 0 : T − 1 i × Π 0 : t − 1 − i → Π t i , given by
F t i ( π 0 : T − 1 i , π 0 : t − 1 − i ) = ∇ π t i q π t + 1 : T i π t i ( b t i , π t i ) , F_t^i\left(\pi_{0:T-1}^i,\pi_{0:t-1}^{-i}\right)=\nabla_{\pi_t^i}q_{\pi_{t+1:T}^i}^{\pi_t^i}\left(b_t^i,\pi_t^i\right), F t i ( π 0 : T − 1 i , π 0 : t − 1 − i ) = ∇ π t i q π t + 1 : T i π t i ( b t i , π t i ) ,
where b t i b_t^i b t i is the focal belief induced by π 0 : t − 1 i \pi^i_{0:t-1} π 0 : t − 1 i and π 0 : t − 1 − i \pi^{-i}_{0:t-1} π 0 : t − 1 − i and q π t + 1 : T − 1 i q^{\pi^i_{t+1:T-1}} q π t + 1 : T − 1 i is defined in Theorem 6 . Thus, F t i F_t^i F t i gives the safest most improving partial direction of the pessimistic Q Q Q -value with respect to π t i \pi_t^i π t i , while keeping the belief fixed.
We may ask whether having the agents follow their respective induced flows improves their value v t i v_t^i v t i . The direction induced by F t i F_t^i F t i is safely improving for timestep t t t to T T T , as all future best-responses are considered in q π t + 1 : T − 1 i q^{\pi^i_{t+1:T-1}} q π t + 1 : T − 1 i . However, it remains unclear whether this improvement is preserved globally across all stages. Indeed, F t i F_t^i F t i is defined under the assumption that the opponent’s past policy remains fixed, as reflected by its dependence on π 0 : t − 1 − i \pi^{-i}_{0:t-1} π 0 : t − 1 − i . When the policies are updated simultaneously across iterations, this assumption may no longer hold: changes to the opponent’s policy at earlier stages can modify the induced belief b t i b_t^i b t i and, consequently, the continuation value at later stages. This creates a situation similar to fictitious play, where both players update their policies simultaneously and each player’s update can therefore affect the optimization problem faced by the other.
Definition 5 (Dual gap). Given a joint policy π t : T − 1 \pi_{t:T-1} π t : T − 1 and the belief state b t i b_t^i b t i induced by the joint policy up to time t − 1 t-1 t − 1 , the dual gap at time t t t is defined as
d t π t : T − 1 ( b t i ) = q t π t + 1 : T − 1 − i ( b t i , π t − i ) − q t π t + 1 : T − 1 i ( b t i , π t i ) . d_t^{\pi_{t:T-1}}(b_t^i) = q_t^{\pi^{-i}_{t+1:T-1}}(b_t^i,\pi_t^{-i}) - q_t^{\pi^i_{t+1:T-1}}(b_t^i,\pi_t^i). d t π t : T − 1 ( b t i ) = q t π t + 1 : T − 1 − i ( b t i , π t − i ) − q t π t + 1 : T − 1 i ( b t i , π t i ) .
Lemma 12 (Local stability of the best response). At any regular policy profile, the best response of the opponent in the constrained subgame rooted at the current policy is locally constant. Consequently, the pessimistic Q Q Q -value
q t i ( b t i , π t i ) = q t i , π t + 1 : T − 1 i ( b t i , π t i ) q_t^i\left(b_t^i,\pi_t^i\right) = q_t^{i,\pi^i_{t+1:T-1}}\left(b_t^i,\pi_t^i\right) q t i ( b t i , π t i ) = q t i , π t + 1 : T − 1 i ( b t i , π t i ) defined in Theorem 6 is differentiable with respect to π t i \pi_t^i π t i in a sufficiently small neighborhood of the current policy.
Proof. At a regular policy profile, the opponent’s best response is unique, since the game is concave-convex and admits a finite set of deterministic policies. Consequently, there exists a neighborhood of the current policy in which this best response remains unchanged. Within this neighborhood, the pessimistic continuation value is therefore evaluated against a fixed best response. The remaining terms in the Bellman recursion are differentiable with respect to π t i \pi_t^i π t i . Hence,
q t i ( b t i , π t i ) q_t^i\left(b_t^i,\pi_t^i\right) q t i ( b t i , π t i )
is differentiable with respect to π t i \pi_t^i π t i . □
The Q-value function is not differentiable everywhere, but this issue is not specific to our setting: the same non-differentiability arises for the dual gap in normal-form games. Since our method uses the same type of local improvement mechanism in policy space, it can handle these points in the same way. Moreover, our discretization does not encounter pathological cases in practice, and the value function explicitly accounts for possible deviations from the current policy. This provides additional protection against numerical instabilities caused by nondifferentiable points and ensures that the improvement step remains robust to such cases.
Lemma 13 (Local improving direction). At a regular policy profile, the direction F t i F_t^i F t i is an improving direction for player i i i ’s pessimistic value at stage t t t . In particular,
d d α q t i ( b t i , π t i + α F t i ) ∣ α = 0 > 0 \left.\frac{d}{d\alpha}q_t^i\left(b_t^i,\pi_t^i+\alpha F_t^i\right)\right|_{\alpha=0} > 0 d α d q t i ( b t i , π t i + α F t i ) α = 0 > 0 whenever π t i \pi_t^i π t i is not locally optimal.
Proof. By Lemma 12 , the local pessimistic Q Q Q -value is differentiable around the current policy. By construction of F t i F_t^i F t i ,
F t i = ∇ π t i q t i ( b t i , π t i ) . F_t^i = \nabla_{\pi_t^i}q_t^i(b_t^i,\pi_t^i). F t i = ∇ π t i q t i ( b t i , π t i ) .
Therefore,
d d α q t i ( b t i , π t i + α F t i ) ∣ α = 0 = ∥ F t i ∥ 2 > 0 \left.\frac{d}{d\alpha}q_t^i\left(b_t^i,\pi_t^i+\alpha F_t^i\right)\right|_{\alpha=0} = \lVert F_t^i\rVert^2 > 0 d α d q t i ( b t i , π t i + α F t i ) α = 0 = ∥ F t i ∥ 2 > 0
whenever F t i ≠ 0 F_t^i \ne0 F t i = 0 .
Lemma 14 (Safe improvement for T = 2 T = 2 T = 2 ). Suppose that T = 2 T = 2 T = 2 . For sufficiently small step sizes, the update of player i i i following the dynamics F t i F_t^i F t i strictly improves her pessimistic value whenever the current policy is not locally optimal.
Proof. Consider the joint policy ( π 0 : 1 1 , k , π 0 : 1 2 , k ) (\pi_{0:1}^{1,k},\pi_{0:1}^{2,k}) ( π 0 : 1 1 , k , π 0 : 1 2 , k ) at iteration k k k . The decision rule π 0 i , k \pi_0^{i,k} π 0 i , k is optimal for the pessimistic continuation problem induced by π 1 i , k \pi_1^{i,k} π 1 i , k .
We first update the last-stage decision rule according to the above dynamics. Since there is no subsequent decision rule, the associated one-stage pessimistic problem is solved directly. Thus, considering any step size α 1 k > 0 \alpha_1^k > 0 α 1 k > 0 , the update
π 1 i , k + 1 = π 1 i , k + α 1 k F 1 i \pi_1^{i,k+1} = \pi_1^{i,k} + \alpha_1^k F_1^i π 1 i , k + 1 = π 1 i , k + α 1 k F 1 i improves the corresponding local pessimistic value, and hence decreases the corresponding local dual gap.
We then update the first-stage decision rule while keeping the newly obtained π 1 i , k + 1 \pi_1^{i,k+1} π 1 i , k + 1 fixed. Define
v k = v 0 i , [ π 0 i , k , π 1 i , k ] , v^k = v_0^{i,[\pi_0^{i,k},\pi_1^{i,k}]}, v k = v 0 i , [ π 0 i , k , π 1 i , k ] , v ~ k = v 0 i , [ π 0 i , k , π 1 i , k + 1 ] , \widetilde{v}^k = v_0^{i,[\pi_0^{i,k},\pi_1^{i,k+1}]}, v k = v 0 i , [ π 0 i , k , π 1 i , k + 1 ] , and
v k + 1 = v 0 i , [ π 0 i , k + 1 , π 1 i , k + 1 ] . v^{k+1} = v_0^{i,[\pi_0^{i,k+1},\pi_1^{i,k+1}]}. v k + 1 = v 0 i , [ π 0 i , k + 1 , π 1 i , k + 1 ] . By construction of the first-stage update, F 0 i F_0^i F 0 i is an improving direction for the local function. Therefore, the newly obtained policy π 0 i , k + 1 \pi_0^{i,k+1} π 0 i , k + 1 strictly improve the overall pessimistic value
π 0 i ↦ v 0 i , [ π 0 i , π 1 i , k + 1 ] , \pi_0^i \mapsto v_0^{i,[\pi_0^i,\pi_1^{i,k+1}]}, π 0 i ↦ v 0 i , [ π 0 i , π 1 i , k + 1 ] , and thus,
v k + 1 > v ~ k . v^{k+1} > \widetilde{v}^k. v k + 1 > v k . It remains to ensure that the improvement at stage t = 0 t = 0 t = 0 is not cancelled by the preceding update at stage t = 1 t = 1 t = 1 . To this end, we regard the stage t = 1 t = 1 t = 1 update as a homotopy
π 1 i , k + 1 ( α ) = π 1 i , k + α F 1 i , α ∈ [ 0 , α ˉ ] . \pi_1^{i,k+1}(\alpha) = \pi_1^{i,k} + \alpha F_1^i,\qquad\alpha\in[0,\bar{\alpha}]. π 1 i , k + 1 ( α ) = π 1 i , k + α F 1 i , α ∈ [ 0 , α ˉ ] . Let
Δ ( α ) = v 0 i , [ π 0 i , k + 1 ( α ) , π 1 i , k + 1 ( α ) ] − v 0 i , [ π 0 i , k , π 1 i , k ] , \Delta(\alpha) = v_0^{i,[\pi_0^{i,k+1}(\alpha),\pi_1^{i,k+1}(\alpha)]} - v_0^{i,[\pi_0^{i,k},\pi_1^{i,k}]}, Δ ( α ) = v 0 i , [ π 0 i , k + 1 ( α ) , π 1 i , k + 1 ( α )] − v 0 i , [ π 0 i , k , π 1 i , k ] ,
where π 0 i , k + 1 ( α ) \pi_{0}^{i,k+1}(\alpha) π 0 i , k + 1 ( α ) denotes the stage t = 0 t=0 t = 0 update computed from the continuation policy π 1 i , k + 1 ( α ) \pi_{1}^{i,k+1}(\alpha) π 1 i , k + 1 ( α ) .
At α = 0 \alpha=0 α = 0 , the continuation policy coincides with the policy at iteration k k k . Since π 0 i , k + 1 \pi_{0}^{i,k+1} π 0 i , k + 1 is an improving direction for the corresponding local problem, we have Δ ( 0 ) > 0 \Delta(0)>0 Δ ( 0 ) > 0 at every non-degenerate point where the stage 0 direction is strictly improving. By continuity of the pessimistic value in the policy and, locally, of the stage 0 update, there exists α ˉ > 0 \bar{\alpha}>0 α ˉ > 0 such that
Δ ( α ) > 0 for all 0 < α < α ˉ . \Delta(\alpha)>0 \qquad\text{for all }0<\alpha<\bar{\alpha}. Δ ( α ) > 0 for all 0 < α < α ˉ .
Hence, the stage 1 step can be chosen sufficiently small so that the improvement obtained at stage 0 is not cancelled by the preceding continuation update. Consequently,
v k + 1 > v k . v^{k+1}>v^k. v k + 1 > v k .
Lemma 15. For a horizon T T T , if the stage wise updates from stage 1 to stage T − 1 T-1 T − 1 can be chosen to strictly improve the pessimistic value, then the update at stage t = 0 t=0 t = 0 can also be chosen so that the complete iteration strictly improves the pessimistic value.
Proof. Assume that the result holds for a horizon T T T . Consider a horizon T + 1 T+1 T + 1 . Starting from the last stage, we apply the construction from Lemma 14 to stages
1 , … , T − 1. 1,\ldots,T-1. 1 , … , T − 1. By the induction hypothesis, the continuation problem from stage 1 onwards can be updated with sufficiently small step sizes so that its pessimistic value is improved.
We then consider stage t = 0 t=0 t = 0 while keeping the resulting continuation policies fixed. The same local argument applies: the continuation pessimistic value induces a differentiable local Q Q Q -value around the current stage t = 0 t=0 t = 0 policy, and the update follows an improving direction of this function.
Finally, the step sizes at stages 1 , … , T − 1 1,\ldots,T-1 1 , … , T − 1 can be chosen sufficiently small so that the improvement produced at stage 0 dominates the change induced by the continuation updates. By continuity, there therefore exist positive step sizes
α 0 k , … , α T k \alpha_0^k,\ldots,\alpha_T^k α 0 k , … , α T k for which the complete iteration yields a strict improvement of the pessimistic value.
Lemma 16. For any starting joint policy π \pi π , there exists a discretized trajectory
ϕ = ( π 1 , k , π 2 , k ) k ≥ 0 \phi=(\pi^{1,k},\pi^{2,k})_{k\geq0} ϕ = ( π 1 , k , π 2 , k ) k ≥ 0 starting from any ( π 1 , 0 , π 2 , 0 ) (\pi^{1,0},\pi^{2,0}) ( π 1 , 0 , π 2 , 0 ) and following the flow induced by ( F 0 : T − 1 i , F 0 : T − 1 − i ) (F_{0:T-1}^{i},F_{0:T-1}^{-i}) ( F 0 : T − 1 i , F 0 : T − 1 − i ) such that the dual gap strictly decreases at every non-degenerate iteration.
Proof. We construct the trajectory iteratively. At iteration k k k , the policy at each stage is updated according to
π t i , k + 1 = π t i , k + α t k F t i ( π 0 : T − 1 i , k , π 0 : T − 1 − i , k ) , \pi_t^{i,k+1}=\pi_t^{i,k}+\alpha_t^k F_t^i\left(\pi_{0:T-1}^{i,k},\pi_{0:T-1}^{-i,k}\right), π t i , k + 1 = π t i , k + α t k F t i ( π 0 : T − 1 i , k , π 0 : T − 1 − i , k ) , with α t k > 0 \alpha_t^k>0 α t k > 0 .
By Lemma 15 , whenever an improvement at an earlier stage could be affected by the updates of the continuation stages, the corresponding continuation step sizes can be chosen sufficiently small so that this improvement is preserved.
Consequently, at every non-degenerate iteration, the step sizes
α 0 k , … , α T − 1 k \alpha_0^k,\ldots,\alpha_{T-1}^k α 0 k , … , α T − 1 k
can be reduced arbitrarily while remaining strictly positive and can be chosen so that the complete iteration strictly improves the pessimistic value. Equivalently, the associated dual gap satisfies
d 0 ( b 0 , ( π 1 , k + 1 , π 2 , k + 1 ) ) < d 0 ( b 0 , ( π 1 , k , π 2 , k ) ) d_0(b_0,(\pi^{1,k+1},\pi^{2,k+1})) < d_0(b_0,(\pi^{1,k},\pi^{2,k})) d 0 ( b 0 , ( π 1 , k + 1 , π 2 , k + 1 )) < d 0 ( b 0 , ( π 1 , k , π 2 , k ))
Starting from any π \pi π , choosing such step sizes at each iteration defines a discretized trajectory ϕ \phi ϕ following the induced flow. Along this trajectory, the dual gap therefore strictly decreases at every non-degenerate iteration.
Figure 3. Example of a situation at T = 2 T=2 T = 2 . The background represents the gradient of the dual gap at t = 0 t=0 t = 0 . The black arrows represent updates of the policy where only π i 0 \pi_i^0 π i 0 is changing. At t = 0 t=0 t = 0 , since i i i has an optimal view of the pessimistic value function, the move strictly improves the global dual gap. The dashed arrows represent updates at t = 1 t=1 t = 1 ; since the update is also influenced by − i -i − i past, nothing guarantees that the update will follow the global dual gap d 0 d_0 d 0 gradient direction. Here, we present an extreme case where the update at t = 1 t=1 t = 1 almost cancels the one at t = 0 t=0 t = 0 . On the left, we do not adapt the step sizes, on the right, we apply the proof such that destructive updates are avoided and we are sure the updates go to the right direction.
We have established the existence of a trajectory following the flow induced by F t i F_t^i F t i . Since the step size can be chosen arbitrarily small, we can construct a sequence of discrete trajectories with vanishing step sizes that increasingly closely approximates the continuous flow. Along this trajectory, the dual gap d 0 d_0 d 0 is non-increasing. It remains to show that the trajectory converges to the set of Nash equilibria.
Lemma 17. Suppose that, at a joint policy π \pi π , a safe local improving direction exists for the overall objective. Then there exists a player i i i and a stage t t t such that the dynamics F t i F_t^i F t i identify a strictly improving direction at the corresponding induced belief state b t i b_t^i b t i .
Proof. We prove the result by contradiction. Consider first the case T = 2 T=2 T = 2 . Suppose that a safe improving direction exists (considering all stages at once), but that no improving direction can be identified inductively at either stage.
In particular, suppose that no improving direction can be identified at t = 0 t=0 t = 0 . Then the improvement cannot be obtained from the current decision alone and must arise from the continuation decision at t = 1 t=1 t = 1 . Hence, there exists an induced belief state b 1 i b_1^i b 1 i , arbitrarily close to the current one, at which a local change of the policy at t = 1 t=1 t = 1 strictly improves the continuation objective.
By the local improvement property at t = 1 t=1 t = 1 , this strict improvement implies the existence of an improving direction at that belief state. Since the continuation value is continuous with respect to the induced belief state, the same improving direction remains improving in a neighborhood of the current belief state. It can therefore be detected at the current belief state, contradicting the assumption that no improving direction can be identified inductively.
Thus, for T = 2 T=2 T = 2 , every safe local improvement is detected at one of the two stages.
The argument extends inductively to an arbitrary finite horizon. Suppose that no improving direction can be identified at any stage. Then, after ruling out an improvement at the current stage, any remaining improvement must arise from the continuation problem. Applying the same argument to this continuation problem yields a later stage at which a strict local improvement exists. By continuity, this improvement must already be detectable at the corresponding current induced belief state, contradicting the assumption.
Therefore, whenever a safe global improving direction exists, the dynamics identify a strictly improving direction at some stage t t t .
The next theorem characterizes the points toward which the continuous dynamics converges.
Theorem 7. The continuous dynamics ϕ \phi ϕ introduced in Lemma 16 converges to the set of Nash equilibria of the game.
Proof. Consider a joint policy
π ∉ N , \pi\notin\mathcal{N}, π ∈ / N , outside of the set of the Nash Equilibria. Since the dual gap vanishes if and only if the joint policy is a Nash equilibrium,
d 0 ( π ) > 0. d_0(\pi) > 0. d 0 ( π ) > 0. D F t i d 0 ( π ) < 0. \mathrm{D}F_t^i d_0(\pi) < 0. D F t i d 0 ( π ) < 0. Therefore, at every joint policy outside N \mathcal{N} N , the dynamics admit a direction that strictly decreases the dual gap. By Lemma 16 , the updates can be chosen sufficiently small so that the simultaneous evolution of the two players does not cancel this strict improvement. Consequently, along the continuous dynamics,
d d τ d 0 ( ϕ ( τ ) ) < 0 whenever ϕ ( τ ) ∉ N . \frac{\mathrm{d}}{\mathrm{d}\tau}d_0(\phi(\tau)) < 0 \qquad\text{whenever } \phi(\tau) \notin\mathcal{N}. d τ d d 0 ( ϕ ( τ )) < 0 whenever ϕ ( τ ) ∈ / N . Thus, the dual gap is a strict Lyapunov function outside the set N \mathcal{N} N .
Because the joint policy space is compact and the dual gap is non-negative, the function
g ( τ ) = d 0 ( ϕ ( τ ) ) g(\tau) = d_0(\phi(\tau)) g ( τ ) = d 0 ( ϕ ( τ )) is monotonically decreasing and bounded from below. Hence, it converges to some g ∞ ≥ 0 g_\infty\ge0 g ∞ ≥ 0 .
Suppose, for contradiction, that
Then ϕ ( τ ) \phi(\tau) ϕ ( τ ) remains outside N \mathcal{N} N for all sufficiently large τ \tau τ . At every such point, the argument above provides a strictly improving direction for the dynamics, and therefore the dual gap must continue to decrease. This contradicts the convergence of g ( τ ) g(\tau) g ( τ ) to the strictly positive limit g ∞ g_\infty g ∞ .
Hence,
and therefore
lim τ → ∞ d 0 ( ϕ ( τ ) ) = 0. \lim_{\tau\to\infty} d_0(\phi(\tau)) = 0. τ → ∞ lim d 0 ( ϕ ( τ )) = 0. Since the dual gap is zero if and only if the joint policy belongs to N \mathcal{N} N , the trajectory ϕ ( τ ) \phi(\tau) ϕ ( τ ) converges to the set of Nash equilibria.
The previous result establishes that the continuous dynamics converge to the set of Nash equilibria. We now relate these continuous trajectories to the discrete-time policy updates considered in practice. In particular, we show that, under the appropriate conditions, the discrete dynamics track the continuous dynamics sufficiently closely to inherit the same convergence property. This connection is formalized in the following theorem.
Proof of Theorem 2. The discrete algorithm can be written as a stochastic approximation of the continuous dynamics introduced in Definition 4. In particular, for each player i i i ,
π i , k + 1 = ( 1 − α k ) π i , k + α k F ~ t i ( π i , k , π − i , k ) + U i , k + 1 . \pi^{i,k+1} = (1-\alpha_k)\pi^{i,k} + \alpha_k \widetilde{F}^{i}_t(\pi^{i,k},\pi^{-i,k}) + U_{i,k+1}. π i , k + 1 = ( 1 − α k ) π i , k + α k F t i ( π i , k , π − i , k ) + U i , k + 1 .
The operator F ~ t i \widetilde{F}^{i}_t F t i is the discrete counterpart of the continuous improving direction F t i F^{i}_t F t i . Both operators perform the same local pessimistic optimization, but they differ in how this optimization is carried out. While F t i F^{i}_t F t i describes the continuous direction of improvement, F ~ t i \widetilde{F}^{i}_t F t i is obtained by solving the stage-wise LPs used by the algorithm. These LPs exploit the uniform continuity of the value function to construct a local approximation of the pessimistic Q Q Q -value. In particular, F ~ t i \widetilde{F}^{i}_t F t i maximizes this local approximation while matching the exact pessimistic value at the current point (see Theorem 6 ). Thus, the LP provides a discrete approximation of the same local optimization characterized by F t i F^{i}_t F t i .
Consequently, the interpolated sequence of policies can be viewed as a stochastic approximation of the continuous system
π ˙ i = F i ( π i , π − i ) . \dot{\pi}^{i} = F^{i}(\pi^{i},\pi^{-i}). π ˙ i = F i ( π i , π − i ) .
Under the Robbins-Monro conditions and the standard assumptions on the noise, the cumulative effect of the stochastic perturbations remains controlled, while the updates continue to explore the policy space. Together with the assumed consistency of the LP operator with the local continuous dynamics, this ensures that the interpolated trajectory is an asymptotic pseudo-trajectory of the flow induced by ( F 1 , F 2 ) (F^{1},F^{2}) ( F 1 , F 2 ) .
Proposition 1.3 of Benaïm et al. [2 ] provides precisely the required connection. It states, under the corresponding stochastic approximation conditions, that the asymptotic behavior of the algorithm is preserved when its iterates are viewed as perturbed solutions of the limiting differential inclusion. Since we have established that the trajectories of this continuous dynamics converge to a Nash equilibrium, the proposition allows us to transfer this convergence result to the discrete algorithm.
By Lemma 7, the limiting continuous dynamics converges to the set N \mathcal{N} N of Nash equilibria. Hence, the only internally chain-transitive invariant set of the limiting dynamics is contained in N \mathcal{N} N . Benaïm et al. [2 ] ’s stochastic approximation result then implies that the limit set of the discrete iterates is almost surely contained in N \mathcal{N} N . Therefore,
dist ( π k , N ) → k → ∞ a . s . 0. \operatorname{dist}(\pi^k,\mathcal{N}) \xrightarrow[k\to\infty]{\mathrm{a.s.}} 0. dist ( π k , N ) a.s. k → ∞ 0.
Thus, the algorithm converges almost surely to the set of Nash equilibria. □ \square □
Extensive Form Game
A Hierarchy of Planners
Escudie et al. [14 ] introduce a hierarchy of planners for zero-sum partially observable stochastic games (zs-POSGs), based on the observation that different planning procedures arise from progressively stronger assumptions about how future decisions are treated during planning. In particular, the hierarchy distinguishes planners according to the information they have access to and the extent to which future decisions—both their own and those of the opponent—are treated as fixed or optimized during planning.
At the two levels relevant here, the hierarchy can be summarized as follows:
Uninformed planner: a planner that additionally knows the opponent’s policy, together with the information available to the focal planner. This setting can be formulated as a transition-independent zero-sum stochastic game, and is closely related to the stochastic-game formulation introduced at the beginning of this paper.
Beyond this operational characterization, we argue that the hierarchy admits a deeper structural interpretation. To make this interpretation explicit, we first consider the example of Sokota et al. [42 ] , which illustrates why a reduction based solely on public policies can fail. In particular, their discussion of the Backward Dependence Problem highlights how future decisions may depend on information and decisions made earlier in the game, even when these dependencies are not captured by the public policy representation alone.
Equilibrium and Dynamic Programming
The distinction between simultaneous- and sequential-move games provides a deeper motivation for the hierarchy of planners introduced by Escudie et al. [14 ] . We illustrate this point by revisiting the example of Sokota et al. [42 ] and comparing it with the approach developed in Escudie et al. [14 ] .
In a simultaneous-move POSG, the equilibrium sought by the dynamic-programming formulation is a Subgame Perfect Nash Equilibrium (SPNE). This is reflected directly in the corresponding Bellman recursion. In the two-player zero-sum case, the backward recursion can be written schematically as
N E ( π 0 1 , π 0 2 ) N E ( π 1 1 , π 1 2 ) ⋯ N E ( π T − 1 1 , π T − 1 2 ) v π 1 , π 2 , NE(\pi_0^1,\pi_0^2)NE(\pi_1^1,\pi_1^2)\cdots NE(\pi_{T-1}^1,\pi_{T-1}^2)v^{\pi^1,\pi^2}, N E ( π 0 1 , π 0 2 ) N E ( π 1 1 , π 1 2 ) ⋯ N E ( π T − 1 1 , π T − 1 2 ) v π 1 , π 2 ,
where N E NE N E denotes a Nash equilibrium of the corresponding subgame. Thus, the equilibrium is constructed recursively, with the decision rules at each stage being optimized within the corresponding subgame. Because the recursion solves each subgame, the resulting strategy profile satisfies the subgame-perfectness requirement.
This correspondence between dynamic programming and SPNE does not hold in the same way for sequential POSGs, and consequently for extensive-form games (EFGs). In an EFG, the Nash equilibrium sought by the game formulation need not be subgame perfect, even after a reduction to public policies.
This distinction is particularly apparent in Kuhn Poker, where the optimal decision rule at the final stage is not deterministic. If the Bellman recursion above is nevertheless applied directly to the sequential game after reducing it to a public-policy representation, the final stage is optimized through a max or min over the available decision rules. This optimization selects a deterministic decision rule at the final stage and therefore fails to capture the dependence of the final decision on deviations at earlier stages. Sokota et al. [42 ] identify the same structural issue in their example of the “Backward Dependence Problem.”
This observation motivates changing the equilibrium formulation rather than simply applying the simultaneous-game Bellman recursion to a sequential game. Nevertheless, an extensive-form game can be transformed into a lossless game for which a Subgame Perfect Nash Equilibrium exists. The resulting formulation is closely related to the reduction introduced at the beginning of this paper.
How should we handle terminal values in a finite-horizon formulation? In an extensive-form game (EFG), terminal nodes may be reached before the last possible time step, whereas the dynamic-programming formulation evaluates the value at the final time step. Without loss of generality, we can postpone the realization of any terminal reward until the final time step by introducing absorbing states. More precisely, whenever a terminal node is reached at time t < T − 1 t < T - 1 t < T − 1 , we transition to an absorbing state and keep the process there until time T − 1 T-1 T − 1 , at which point the corresponding terminal reward is received. This transformation preserves the value of every policy profile while ensuring that all rewards are realized at the final time step. This is done for readability and to maintain consistency across the different game formulations, thereby simplifying the notation and equations.
Definition 6. Let i i i be a player. We define the associated one-sided EFG (oEFG) as
E i ≔ ( I , D , H , H k , D t i , u ) , \mathcal{E}^{i} \coloneqq(\mathcal{I},\mathcal{D},\mathbf{H},\mathbf{H}^{k},\mathcal{D}^{i}_{t},u), E i : = ( I , D , H , H k , D t i , u ) ,
where the components are defined as follows:
π 0 : t = { π 0 1 , π 0 2 , … , π t k } , \pi_{0:t} = \{\pi^{1}_{0},\pi^{2}_{0},\ldots,\pi^{k}_{t}\}, π 0 : t = { π 0 1 , π 0 2 , … , π t k } ,
where k k k denotes the player k k k . A child node π ′ \pi' π ′ is accessible from π \pi π if
∃ π t k such that π ′ = [ π , π t k ] . \exists\pi^{k}_{t} \text{ such that } \pi' = [\pi,\pi^{k}_{t}]. ∃ π t k such that π ′ = [ π , π t k ] .
H k ( π 0 : t ) = { π 0 : t k if k = i , π 0 : t otherwise. \mathbf{H}^{k}(\pi_{0:t}) =
\begin{cases}
\pi^{k}_{0:t} & \text{if } k=i,\\
\pi_{0:t} & \text{otherwise.}
\end{cases} H k ( π 0 : t ) = { π 0 : t k π 0 : t if k = i , otherwise.
Thus, the focal player i i i observes only her own policy prefix, whereas the opponent − i -i − i observes the complete joint policy prefix.
u ( π 0 : T ) ≔ v π 0 : T 1 , π 0 : T 2 . u(\pi_{0:T}) \coloneqq v^{\pi^{1}_{0:T},\pi^{2}_{0:T}}. u ( π 0 : T ) : = v π 0 : T 1 , π 0 : T 2 .
The players make their decisions sequentially, with i i i choosing first and − i -i − i choosing after observing the complete policy prefix of i i i . Consequently, the value of the game is characterized by a max-min optimization: i i i chooses a decision rule to maximize the value, while − i -i − i observes this choice and subsequently chooses a decision rule to minimize it.
Under this construction, i i i has access only to her own policy, whereas − i -i − i has access to both players’ policies. We then show that any zero-sum EFG admits a lossless reduction to the corresponding zero-sum oEFG.
Theorem 8. Let E \mathcal{E} E be a zero-sum extensive-form game and let i i i be the focal player. The reduction
T E → E i \mathcal{T}_{\mathcal{E}\rightarrow\mathcal{E}^{i}} T E → E i that projects E \mathcal{E} E onto the one-sided EFG E i \mathcal{E}^{i} E i is lossless for player i i i . In particular, it preserves the value of every joint policy and the focal player’s maximin value and optimal policies.
Proof. We establish the result by showing that the reduction preserves (i) the correspondence between joint policies and paths in the decision tree, (ii) the associated values, and (iii) the information available to the focal player.
Policy and path correspondence. Consider a joint policy
π 0 : T = ( π 0 : T i ; π 0 : T − i ) \pi_{0:T} = \left(\pi^{i}_{0:T};\pi^{-i}_{0:T}\right) π 0 : T = ( π 0 : T i ; π 0 : T − i )
in the original EFG E \mathcal{E} E . The reduction associates with this joint policy a policy π ~ \tilde{\pi} π ~ in the one-sided EFG E i \mathcal{E}^{i} E i .
At each node corresponding to a policy prefix π 0 : t \pi_{0:t} π 0 : t , the next decision of the focal player is determined by her own policy prefix π 0 : t i \pi^{i}_{0:t} π 0 : t i , whereas the next decision of the opponent is determined by the complete policy prefix π 0 : t \pi_{0:t} π 0 : t . Thus, the complete joint policy uniquely determines a path in the decision tree D \mathcal{D} D , and conversely, a path in D \mathcal{D} D specifies the sequence of decision rules constituting the corresponding joint policy. Value preservation. By construction, the terminal node reached by the path associated with π 0 : T \pi_{0:T} π 0 : T has reward
u ( π 0 : T ) ≔ v π 0 : T i , π 0 : T − i . u(\pi_{0:T}) \coloneqq v^{\pi^i_{0:T},\pi^{-i}_{0:T}}. u ( π 0 : T ) : = v π 0 : T i , π 0 : T − i .
Consequently, the expected value induced by any joint policy is unchanged by the reduction:
u ( π ~ ) = v π 0 : T i , π 0 : T − i . u(\tilde{\pi}) = v^{\pi^i_{0:T},\pi^{-i}_{0:T}}. u ( π ~ ) = v π 0 : T i , π 0 : T − i .
Hence, optimizing over corresponding policies in the two representations yields the same payoff. In particular, the reduction does not introduce or remove any payoff-relevant trajectories.
Information preservation for the focal player. The reduction is one-sided precisely because it preserves the information available to the focal player while explicitly exposing additional information to the opponent. In E i \mathcal{E}^i E i , player i i i observes only her own policy prefix through the information partition H i \mathcal{H}^i H i :
H i ( π 0 : t ) = π 0 : t i . \mathcal{H}^i(\pi_{0:t}) = \pi^i_{0:t}. H i ( π 0 : t ) = π 0 : t i .
This is exactly the information on which her decision rule is allowed to depend. By contrast, the opponent observes the complete policy prefix,
H − i ( π 0 : t ) = π 0 : t , \mathcal{H}^{-i}(\pi_{0:t}) = \pi_{0:t}, H − i ( π 0 : t ) = π 0 : t ,
and can therefore condition its decision on the focal player’s previous decisions. The opponent thus acts as an informed best responder. Since the theorem concerns losslessness for player i i i , granting this additional information to the opponent does not alter the focal player’s policy space or information structure; rather, it makes the opponent’s minimization explicit.
Preservation of the focal player’s maximin problem. Because the game is zero-sum, the value associated with a joint policy can be written as
v π i , π − i . v^{\pi^i,\pi^{-i}}. v π i , π − i .
The focal player’s security problem in the original game is therefore
max π i min π − i v π i , π − i . \max_{\pi^i}\min_{\pi^{-i}} v^{\pi^i,\pi^{-i}}. π i max π − i min v π i , π − i .
The policy and value correspondence established above implies that the same optimization problem is represented in E i \mathcal{E}^i E i :
max π ~ i min π ~ − i u ( π ~ ) . \max_{\tilde{\pi}^i}\min_{\tilde{\pi}^{-i}} u(\tilde{\pi}). π ~ i max π ~ − i min u ( π ~ ) .
Thus, the two formulations have the same maximin value, and a policy is optimal for player i i i in the original EFG if and only if its corresponding policy is optimal in the one-sided EFG.
Finally, by the minimax theorem for finite zero-sum games, the maximin value coincides with the value attained at a Nash equilibrium. Hence, the focal player’s equilibrium value and the set of focal-player maximin strategies are preserved by the reduction, even though the one-sided representation does not claim to preserve the opponent’s information structure or the full set of equilibrium strategies.
Theorem 9. Under the convention introduced in Definition 6, the one-sided EFG E i \mathcal{E}^i E i admits a unilateral Subgame Perfect Nash Equilibrium. In particular, its value satisfies the following Bellman recursion:
v t ∗ , i ( π 0 : t − 1 i ) = max π t i min π 0 : T − 1 − i v t + 1 ∗ , i ( π 0 : t i ) , v_t^{*,i}\left(\pi_{0:t-1}^i\right)=\max_{\pi_t^i}\min_{\pi_{0:T-1}^{-i}}v_{t+1}^{*,i}\left(\pi_{0:t}^i\right), v t ∗ , i ( π 0 : t − 1 i ) = π t i max π 0 : T − 1 − i min v t + 1 ∗ , i ( π 0 : t i ) ,
where v t ∗ , i ( π 0 : t − 1 i ) v_t^{*,i}\left(\pi_{0:t-1}^i\right) v t ∗ , i ( π 0 : t − 1 i ) denotes the optimal continuation value for player i i i after fixing her policy prefix π 0 : t − 1 i \pi_{0:t-1}^i π 0 : t − 1 i .
At the final decision stage, the recursion reduces to
v T − 1 ∗ , i ( π 0 : T − 2 i ) = max π T − 1 i min π 0 : T − 1 − i u T − 1 ( π 0 : T − 1 i , π 0 : T − 1 − i ) . v_{T-1}^{*,i}\left(\pi_{0:T-2}^i\right)=\max_{\pi_{T-1}^i}\min_{\pi_{0:T-1}^{-i}}u_{T-1}\left(\pi_{0:T-1}^i,\pi_{0:T-1}^{-i}\right). v T − 1 ∗ , i ( π 0 : T − 2 i ) = π T − 1 i max π 0 : T − 1 − i min u T − 1 ( π 0 : T − 1 i , π 0 : T − 1 − i ) .
Proof. We prove by backward induction the stronger statement ( ∗ ) (*) ( ∗ ) ,
v t ∗ , i ( π 0 : t − 1 i ) = max π t : T − 1 i min π 0 : T − 1 − i u ( [ π 0 : t − 1 i , π t : T − 1 i ] , π 0 : T − 1 − i ) v_t^{*,i}\left(\pi_{0:t-1}^i\right)=\max_{\pi_{t:T-1}^i}\min_{\pi_{0:T-1}^{-i}}u\left(\left[\pi_{0:t-1}^i,\pi_{t:T-1}^i\right],\pi_{0:T-1}^{-i}\right) v t ∗ , i ( π 0 : t − 1 i ) = π t : T − 1 i max π 0 : T − 1 − i min u ( [ π 0 : t − 1 i , π t : T − 1 i ] , π 0 : T − 1 − i )
for every t t t .
Base case. At t = T − 1 t=T-1 t = T − 1 , there is no future decision of player i i i after π T − 1 i \pi_{T-1}^i π T − 1 i . Therefore, by definition,
v T − 1 ∗ , i ( π 0 : T − 2 i ) = max π T − 1 i min π 0 : T − 1 − i u ( [ π 0 : T − 2 i , π T − 1 i ] , π 0 : T − 1 − i ) , v_{T-1}^{*,i}\left(\pi_{0:T-2}^i\right)=\max_{\pi_{T-1}^i}\min_{\pi_{0:T-1}^{-i}}u\left(\left[\pi_{0:T-2}^i,\pi_{T-1}^i\right],\pi_{0:T-1}^{-i}\right), v T − 1 ∗ , i ( π 0 : T − 2 i ) = π T − 1 i max π 0 : T − 1 − i min u ( [ π 0 : T − 2 i , π T − 1 i ] , π 0 : T − 1 − i ) ,
so property ( ∗ ) (*) ( ∗ ) holds.
Induction step. Assume that ( ∗ ) (*) ( ∗ ) holds at time t + 1 t+1 t + 1 . Then
v t ∗ , i ( π 0 : t − 1 i ) = max π t i min π 0 : T − 1 − i v t + 1 ∗ , i ( π 0 : t i ) = max π t i min π 0 : T − 1 − i max π t + 1 : T − 1 i min π 0 : T − 1 − i u ( [ π 0 : t − 1 i , π t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) . \begin{aligned}
v_t^{*,i}\left(\pi_{0:t-1}^i\right)
&=\max_{\pi_t^i}\min_{\pi_{0:T-1}^{-i}}v_{t+1}^{*,i}\left(\pi_{0:t}^i\right)\\
&=\max_{\pi_t^i}\min_{\pi_{0:T-1}^{-i}}\max_{\pi_{t+1:T-1}^i}\min_{\pi_{0:T-1}^{-i}}u\left(\left[\pi_{0:t-1}^i,\pi_t^i,\pi_{t+1:T-1}^i\right],\pi_{0:T-1}^{-i}\right).
\end{aligned} v t ∗ , i ( π 0 : t − 1 i ) = π t i max π 0 : T − 1 − i min v t + 1 ∗ , i ( π 0 : t i ) = π t i max π 0 : T − 1 − i min π t + 1 : T − 1 i max π 0 : T − 1 − i min u ( [ π 0 : t − 1 i , π t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) .
We now justify the exchange of the middle min and max. Fix a prefix π 0 : t i \pi^i_{0:t} π 0 : t i . Player i i i chooses a complete continuation policy
π t + 1 : T − 1 i , \pi^i_{t+1:T-1}, π t + 1 : T − 1 i ,
while player − i -i − i chooses a complete policy
π 0 : T − 1 − i . \pi^{-i}_{0:T-1}. π 0 : T − 1 − i .
For fixed π 0 : t i \pi^i_{0:t} π 0 : t i , let the payoff of the corresponding pure-strategy pair be
U ( π t + 1 : T − 1 i , π 0 : T − 1 − i ) = u ( [ π 0 : t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) . U\left(\pi^i_{t+1:T-1},\pi^{-i}_{0:T-1}\right)=u\left([\pi^i_{0:t},\pi^i_{t+1:T-1}],\pi^{-i}_{0:T-1}\right). U ( π t + 1 : T − 1 i , π 0 : T − 1 − i ) = u ( [ π 0 : t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) .
When the two players randomize over these complete policies, the expected payoff is bilinear in their mixed strategies. Hence, by the minimax theorem,
min π 0 : T − 1 − i max π t + 1 : T − 1 i U = max π t + 1 : T − 1 i min π 0 : T − 1 − i U . \min_{\pi^{-i}_{0:T-1}}\max_{\pi^i_{t+1:T-1}} U
=
\max_{\pi^i_{t+1:T-1}}\min_{\pi^{-i}_{0:T-1}} U. π 0 : T − 1 − i min π t + 1 : T − 1 i max U = π t + 1 : T − 1 i max π 0 : T − 1 − i min U .
This is the same minimax argument used in Delage et al. [7 ] . Importantly, the argument is applied only after fixing the focal player’s prefix π 0 : t i \pi^i_{0:t} π 0 : t i ; the continuation policies of the two players then constitute the strategy spaces of the induced zero-sum normal-form game.
Applying this equality inside the backward recursion gives
v t ∗ , i ( π 0 : t − 1 i ) = max π t i max π t + 1 : T − 1 i min π 0 : T − 1 − i u ( [ π 0 : t − 1 i , π t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) = max π t : T − 1 i min π 0 : T − 1 − i u ( [ π 0 : t − 1 i , π t : T − 1 i ] , π 0 : T − 1 − i ) . \begin{aligned}
v_t^{*,i}\left(\pi^i_{0:t-1}\right)
&=\max_{\pi^i_t}\max_{\pi^i_{t+1:T-1}}\min_{\pi^{-i}_{0:T-1}}
u\left([\pi^i_{0:t-1},\pi^i_t,\pi^i_{t+1:T-1}],\pi^{-i}_{0:T-1}\right)\\
&=\max_{\pi^i_{t:T-1}}\min_{\pi^{-i}_{0:T-1}}
u\left([\pi^i_{0:t-1},\pi^i_{t:T-1}],\pi^{-i}_{0:T-1}\right).
\end{aligned} v t ∗ , i ( π 0 : t − 1 i ) = π t i max π t + 1 : T − 1 i max π 0 : T − 1 − i min u ( [ π 0 : t − 1 i , π t i , π t + 1 : T − 1 i ] , π 0 : T − 1 − i ) = π t : T − 1 i max π 0 : T − 1 − i min u ( [ π 0 : t − 1 i , π t : T − 1 i ] , π 0 : T − 1 − i ) .
This is precisely property ( ∗ ) (*) ( ∗ ) at time t t t , completing the induction.
Finally, applying ( ∗ ) (*) ( ∗ ) at t = 0 t=0 t = 0 yields
v 0 ∗ , i = max π 0 : T − 1 i min π 0 : T − 1 − i u ( π 0 : T − 1 i , π 0 : T − 1 − i ) . v_0^{*,i}=\max_{\pi^i_{0:T-1}}\min_{\pi^{-i}_{0:T-1}}u\left(\pi^i_{0:T-1},\pi^{-i}_{0:T-1}\right). v 0 ∗ , i = π 0 : T − 1 i max π 0 : T − 1 − i min u ( π 0 : T − 1 i , π 0 : T − 1 − i ) .
Thus, the policy generated by the Bellman recursion is a maximin-optimal policy for player i i i . Since the opponent observes the complete policy prefix of player i i i , this sequential maximin construction corresponds to the unilateral Subgame Perfect Nash Equilibrium of the one-sided EFG. Hence, the Bellman recursion computes the equilibrium value and an equilibrium strategy for the focal player.
A few observations follow from this construction. First, by reducing an EFG to a one-sided EFG, we obtain a well-defined notion of a proper subgame for the sequential game. This allows us to formulate and compute a Subgame Perfect Nash Equilibrium, thereby addressing the backward-dependence issue identified by Sokota et al. [42 ] . In particular, the one-sided construction makes the information available to the two players explicit and ensures that the continuation problem at each stage is formulated as the appropriate sequential zero-sum game.
Second, this result is closely related to Theorem 3 of Escudie et al. [14 ] . While our proof is formulated directly in terms of the decision tree and does not explicitly use the occupancy-state representation, the correspondence between the two formulations is immediate: the nodes of the one-sided EFG can equivalently be represented by the corresponding occupancy states. Thus, the construction provides an alternative, more explicit interpretation of the same underlying reduction.
The main distinction is the scope in which this construction is required. The one-sided reduction is necessary when dealing with sequential games, such as EFGs or sequential POSGs, because future decisions may depend on previously revealed decisions and therefore cannot in general be optimized independently through the standard simultaneous-move Bellman recursion. In contrast, most of the games considered in this paper are simultaneous-move POSGs. In that setting, the standard dynamic-programming formulation already corresponds to the appropriate subgame-perfect solution concept, and the additional one-sided reduction is therefore unnecessary. The relationship between these two cases is illustrated in Figure 4 .
Figure 4. T G → G ′ \mathcal{T}_{\mathcal{G}\to\mathcal{G}'} T G → G ′ denotes the reduction from game G \mathcal{G} G to game G ′ \mathcal{G}' G ′ . The reduction T P O S G → E F G \mathcal{T}_{POSG\to EFG} T P O S G → E F G is almost transparent: it simply reformulates the POSG as an extensive-form game (EFG). However, unlike T P O S G → S G \mathcal{T}_{POSG\to SG} T P O S G → S G , this reduction does not induce an equilibrium concept that can be characterized inductively in the reduced game. The composition T P O S G → E F G ∘ T E F G → O E F G \mathcal{T}_{POSG\to EFG}\circ\mathcal{T}_{EFG\to OEFG} T P O S G → E F G ∘ T E F G → O E F G corresponds to the focal-planner reduction introduced in Escudie et al. [14 ] .
We work with the uninformed planner introduced by Escudie et al. [14 ] because deviations in the past cannot depend on the public history. If we were to use an informed planner instead, the resulting optimization would allow a different deviation for each public history. This would effectively give the best response access to the public history before the corresponding decision is made, which is not available to the player and would therefore be inconsistent with the information structure of the game.
Experiments
We extend Algorithm 1 to extensive-form games by adapting the local policy-improvement step to account for deviations from decisions made at earlier stages of the game. In particular, the linear program is modified to retain the relevant information about past decisions when computing the current deviation, allowing the local improvement procedure to operate directly on the extensive-form representation.
To obtain a deviation model consistent with the intended information structure, we include public histories in the support of the belief representation. The deviation is therefore defined with respect to the information available to the player rather than separately for each public history. Without this restriction, the optimization could effectively select a different deviation for every public history, leading to an overly pessimistic evaluation that does not correspond to the intended player model.
We implemented this extension and evaluated it on Kuhn Poker. The resulting algorithm exhibits convergence to the expected equilibrium behavior in our experiments. However, the current implementation is primarily intended as a proof-of-concept: the code requires further cleanup and validation before the experimental results can be presented as part of the main empirical evaluation. We therefore leave a more systematic experimental study of the extensive-form extension to future work.
Experiments
Baselines
PBVI in zs-SG In a POMDP, the value function is defined over the belief simplex and is piecewise-linear and convex, making exact value iteration intractable. PBVI addresses this issue by restricting computation to a finite set of representative beliefs. At each iteration, Bellman backups are performed only on this set, yielding an approximate value function that is accurate in the vicinity of the sampled beliefs while remaining tractable.
PBVI is inherently a single-agent method. In adversarial settings, it is therefore applied to a one-sided (focal-planner) surrogate, where one player is optimized while the opponent is treated as part of the environment. Two levels of sampling arise. First, beliefs are expanded via forward simulation to cover reachable regions of the belief space. Second, in the one-sided reduction, the opponent is simulated (e.g., via randomized policies), so that the focal player optimizes against sampled behaviors. This relies on the assumption that relevant opponent responses lie near those induced by sampling.
Each PBVI backup requires a maximization over actions and observations, which in adversarial settings leads to linear programs for worst-case evaluation. The number of α \alpha α -vectors grows rapidly with iterations, increasing the size of these programs. Consequently, the Bellman operator quickly becomes intractable despite the point-based approximation.
CFR in POSG. Counterfactual Regret Minimization (CFR) is an iterative algorithm for solving extensive-form games (EFGs) that minimizes counterfactual regret at each information set, yielding convergence to a Nash equilibrium in two-player zero-sum settings. At each iteration, CFR eval uates the current strategy profile, computes counterfactual values, and updates strategies via regret matching.
The connection between POSGs and EFGs has been established in [22 ] , laying the groundwork for the application of extensive-form techniques such as CFR. Notably, the theoretical objects introduced in our paper naturally embed CFR and yield a refined variant tailored to POSGs. To make this connection explicit, Table 3 presents a correspondence between standard EFG notions and their POSG counterparts, thereby providing a bridge for transferring the algorithm. The relevant notation is summarized in Table 3 .
Table 3. Translation from EFG to POSG. For more information, we refer the reader to [22 ] . We connect the history h h h in EFG to the pair ( s , h ) (s,h) ( s , h ) in POSG since the reward is not associated to the history but to the state in POSG. The quantity v M π ( s , h ) v_M^\pi(s,h) v M π ( s , h ) is formally defined in [6 ] , we refer the reader for more information. It is simply the expected cumulated value a player can get at this pair.
From [50 , 28 ] , we adapt the key ingredients of CFR to the POSG setting. We first define the (instantaneous) regret at ( s t , h t ) (s_t,h_t) ( s t , h t ) for player − i -i − i when deviating only at h − i , t h_{-i,t} h − i , t to action a − i , t a_{-i,t} a − i , t :
r M ( s t , h t , a i , t ) = v M π h i , t → a i , t ( s t , h t ) − v M π ( s t , h t ) . r_M(s_t,h_t,a_{i,t}) = v_M^{\pi_{h_i,t\to a_{i,t}}}(s_t,h_t) - v_M^\pi(s_t,h_t). r M ( s t , h t , a i , t ) = v M π h i , t → a i , t ( s t , h t ) − v M π ( s t , h t ) .
In contrast to EFGs, where regret is indexed by histories h h h , in POSGs it is defined over ( s t , h t ) (s_t,h_t) ( s t , h t ) since rewards depend on the (hidden) state s t s_t s t . The history remains necessary to condition the belief over states.
Aggregating over histories that share the same private history h i , t h_{i,t} h i , t yields a vector-valued regret:
r M h i , t → a i , t ( s t , h i , t ) = v M π h − i , t → a − i , t ( s t , h i , t , h − i , t ) − v M π ( s t , h i , t , h − i , t ) , r_M^{h_{i,t}\to a_{i,t}}(s_t,h_{i,t}) = v_M^{\pi_{h_{-i,t}\to a_{-i,t}}}(s_t,h_{i,t},h_{-i,t}) - v_M^\pi(s_t,h_{i,t},h_{-i,t}), r M h i , t → a i , t ( s t , h i , t ) = v M π h − i , t → a − i , t ( s t , h i , t , h − i , t ) − v M π ( s t , h i , t , h − i , t ) ,
which is a vector over C i C_i C i (one coordinate per state). Using the conditional state c i c_i c i notation, we recover a scalar regret:
R M h − i , t → a − i , t = r M h − i , t → a − i , t ⋅ c i . R_M^{h_{-i,t}\to a_{-i,t}} = r_M^{h_{-i,t}\to a_{-i,t}}\cdot c_i. R M h − i , t → a − i , t = r M h − i , t → a − i , t ⋅ c i .
This corresponds to the EFG quantity
r E F G ( I , a ) = ∑ h ∈ I ( v i ( σ I → a , h ) − v i ( σ , h ) ) . r_{EFG}(I,a) = \sum_{h\in I}\left(v_i(\sigma_{I\to a},h)-v_i(\sigma,h)\right). r E F G ( I , a ) = h ∈ I ∑ ( v i ( σ I → a , h ) − v i ( σ , h ) ) .
where the summation over histories is replaced by expectation under the counterfactual occupancy.
The policy is then updated via regret matching:
π − i , n e w ( a − i , t ∣ h − i , t ) = [ R M h − i , t → a − i , t ] + ∑ a − i , t ′ [ R M h − i , t → a − i , t ′ ] + . \pi_{-i,\mathrm{new}}(a_{-i,t}\mid h_{-i,t}) = \frac{\left[R_M^{h_{-i,t}\to a_{-i,t}}\right]_+}{\sum_{a'_{-i,t}}\left[R_M^{h_{-i,t}\to a'_{-i,t}}\right]_+}. π − i , new ( a − i , t ∣ h − i , t ) = ∑ a − i , t ′ [ R M h − i , t → a − i , t ′ ] + [ R M h − i , t → a − i , t ] + .
The regret of player − i -i − i is inherently vector-valued, as it is defined conditionally on the hidden state. The conditional state c i c_i c i acts as a belief, projecting this vector onto a scalar quantity, exactly as counterfactual reach probabilities do in EFGs. This establishes a direct connection with the focal-planner view: regret minimization operates on belief-weighted values, consistent with optimizing a surrogate game for a fixed opponent.
Our framework can be interpreted as performing regret minimization directly in the occupancy space. Instead of explicitly maintaining regrets per history, we operate on regret functions over counterfactual occupancy states, and policy updates correspond to regret matching under these occupancy-induced weights. This yields a compact implementation that avoids explicit enumeration of histories.
Implementation Details
The results presented in this paper were run on CPU (AMD Ryzen 7 PRO).
Table 5. A snapshot of empirical results with no pruning mechanism applied (see [14 , 12 ] . For each game, horizon and algorithm, we report time, value and exploitability ϵ \epsilon ϵ associated with the computed ϵ \epsilon ϵ -Nash equilibrium. OOT occurs when the target exploitability threshold cannot be reached within the prescribed time limit, while OOM means that the algorithms ran out of memory. magenta = lowest exploitability value per benchmark, while ‘−’ means the time budget for computing the exploitability has been exceeded.