betaFeedback

WorksComputer Science

Conservative Policy Iteration For Zero-Sum POSGs

Abstract

Occupancy-state reductions make dynamic programming possible for zero-sum partially observable stochastic games (zs-POSGs). Existing point-based solvers usually optimise a central value function. This restores Bellman recursion, but it requires point-based updates over high-dimensional occupancy spaces. We introduce an approximate policy-iteration algorithm for finite-horizon zs-POSGs. The method maintains one policy per player and updates both jointly along occupancy trajectories induced by conservative policy updates. Instead of approximating a full central value function, each update uses a single supporting hyperplane induced by the current joint policy. The algorithm alternates local policy improvements, conservative updates, and persistent exploration. Computation is therefore concentrated on occupancy regions where the current joint policy is exploitable. On finite-horizon zero-sum POSG benchmarks, the method is competitive at small horizons and often improves the runtime-exploitability trade-off at larger horizons compared with PBVI, HSVI, and CFR+.

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,Z0,p,(ri)i∈I,T,b0)\mathcal{M} = (\mathcal{I},\mathcal{S},\mathcal{A},\mathcal{Z},\mathcal{Z}^{0},p,(r^{i})_{i\in\mathcal{I}},T,b_{0}), where I={1,2}\mathcal{I} = \{1,2\}, S\mathcal{S} is a finite state space, A=×i∈IAi\mathcal{A} = \times_{i\in\mathcal{I}}\mathcal{A}^{i} is the joint action space, Z=×i∈IZi\mathcal{Z} = \times_{i\in\mathcal{I}}\mathcal{Z}^{i} is the joint private observation space, Z0\mathcal{Z}^{0} is the public observation space, p:S×A×Z0×Z→Sp:\mathcal{S}\times\mathcal{A}\times\mathcal{Z}^{0}\times\mathcal{Z}\to\mathcal{S} is the transition kernel, ri:S×A→Rr^{i}:\mathcal{S}\times\mathcal{A}\to\mathbb{R} is player ii’s reward, r2=−r1r^{2}=-r^{1}, b0∈Δ(S)b_{0}\in\Delta(\mathcal{S}) is the initial state distribution, and TT is the horizon.

The game unfolds over stages t=0,…,T−1t = 0,\ldots,T-1. At stage tt, the players choose ata_t, each player ii receives ri(st,at)r^{i}(s_t,a_t), and the game samples (st+1,zt+10,zt+1)(s_{t+1},z^{0}_{t+1},z_{t+1}) according to p(⋅∣st,at)p(\cdot\mid s_t,a_t). Because the state is hidden, ii acts from its private history htih^{i}_{t} and the public history ht0h^{0}_{t}. These histories are empty at t=0t=0. For t≥1t\geq1, hti=a0iz1i⋯at−1iztih^{i}_{t}=a^{i}_{0}z^{i}_{1}\cdots a^{i}_{t-1}z^{i}_{t} records ii’s past actions and private observations, and ht0=z10⋯zt0h^{0}_{t}=z^{0}_{1}\cdots z^{0}_{t} records the public observations. We write ht=(ht1,ht2)h_t=(h^{1}_{t},h^{2}_{t}) for a joint private history, with reachable sets Hti\mathcal{H}^{i}_{t}, Ht\mathcal{H}_{t}, and Ht0\mathcal{H}^{0}_{t}.

A decision rule for player ii is a map πti:Hti×Ht0→Δ(Ai)\pi_t^i : \mathcal{H}_t^i \times\mathcal{H}_t^0 \to\Delta(\mathcal{A}_i). A joint decision rule is πt=(πt1,πt2)∈Πt≔Πt1×Πt2\pi_t = (\pi_t^1,\pi_t^2) \in\Pi_t \coloneqq\Pi_t^1 \times\Pi_t^2. A behavioural policy profile is π=(π0,…,πT−1)∈Π\pi= (\pi_0,\ldots,\pi_{T-1}) \in\Pi. We write πi∈Πi\pi^i \in\Pi^i for a full behavioural policy of player ii. We write πt:Ti∈Πt:Ti\pi_{t:T}^i \in\Pi_{t:T}^i for player ii’s policy suffix and πt:T∈Πt:T\pi_{t:T} \in\Pi_{t:T} for a policy-profile suffix from stage tt onward. We write π0:ti∈Π0:ti\pi_{0:t}^i \in\Pi_{0:t}^i for player ii’s policy prefix and π0:t∈Π0:t\pi_{0:t} \in\Pi_{0:t} for a policy-profile prefix.

Policies are evaluated by expected cumulative payoff. Given b0b_0, ii’s payoff under π\pi is Jiπ≔Eb0,p,π[∑k=0T−1ri(Sk,Ak)]J_i^\pi\coloneqq\mathbb{E}_{b_0,p,\pi}\left[\sum_{k=0}^{T-1} r^i(S_k,A_k)\right]. Since r2=−r1r^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,

v01,∗(b0)=max⁡π1∈Π1min⁡π2∈Π2J1(π1,π2)=min⁡π2∈Π2max⁡π1∈Π1J1(π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)}.

A policy profile attaining this value is a Nash equilibrium of the induced zero-sum game. Equivalently, player ii’s component is maximin optimal for ii’s payoff for any i∈Ii \in\mathcal{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}, the central occupancy state is ot(π0:t)=Pb0,p,π0:t(St,Ht,Ht0)o_t(\pi_{0:t})=\mathbb{P}_{b_0,p,\pi_{0:t}}(S_t,H_t,H_t^0). We write oto_t when the prefix is clear. It belongs to Ot⊆Δ(S×Ht×Ht0)\mathcal{O}_t \subseteq\Delta(\mathcal{S}\times\mathcal{H}_t\times\mathcal{H}_t^0). Although oto_t is not observed by either player, it is Markovian for a central planner. Given oto_t and πt\pi_t, the next occupancy is τt(ot,πt)=Pot,πt(St+1,Ht+1,Ht+10)\tau_t(o_t,\pi_t)=\mathbb{P}_{o_t,\pi_t}(S_{t+1},H_{t+1},H_{t+1}^0). Player ii’s one-step expected reward is ρi,t(ot,πt)=Eot,πt[ri(St,At)]\rho_{i,t}(o_t,\pi_t)=\mathbb{E}_{o_t,\pi_t}[r^i(S_t,A_t)].

The central occupancy state restores Bellman’s principle for the zero-sum value. With vT1,∗(⋅)=0v_T^{1,*}(\cdot)=0, the central dynamic program is

References

  1. [1]Karl J. Aström. Optimal control of Markov decision processes with incomplete state estimation. Journal of Mathematical Analysis and Applications, 10:174–205, 1965.
  2. [2]Michel Benaïm, Josef Hofbauer, and Sylvain Sorin. Stochastic approximations and differential inclusions. SIAM Journal on Control and Optimization, 44(1):328–348, 2005. doi: 10.1137/S0363012904439301. URL https://doi.org/10.1137/S0363012904439301.
  3. [3]Dimitri P. Bertsekas and John N. Tsitsiklis. Neuro-dynamic programming., volume 3 of Optimization and neural computation series. Athena Scientific, 1996. ISBN 1886529108.
  4. [4]Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learning and search for imperfect-information games. In Advances in Neural Information Processing Systems (NeurIPS), 2020.arxiv.org/abs/2007.13544
  5. [5]Olivier Buffet, Jilles Steeve Dibangoye, Abdallah Safdine, and Vincent Thomas. ε-optimally solving zs-POSGs using Bellman’s optimality principle. Technical report, Inria Nancy Grand-Est, 2020.
  6. [6]Rafael F. Cunha, Jacopo Castellini, Johan Peralez, and Jilles Steeve Dibangoye. On convex optimal value functions for POSGs. arXiv preprint arXiv:2311.09459, 2023.arxiv.org/abs/2311.09459
  7. [7]Aurélien Delage, Olivier Buffet, Jilles Steeve Dibangoye, and Abdallah Saffidine. HSVI can solve zero-sum partially observable stochastic games. Dynamic Games and Applications, pp. 1–55, 2023.arxiv.org/abs/2210.14640
  8. [10]Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), pp. 90–96, 2013.
  9. [12]Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research, 55: 443–497, 2016a.
  10. [14]Erwan C. Escudie, Matthia Sabatelli, Olivier Buffet, and Jilles Steeve Dibangoye. ε-optimally solving two-player zero-sum posgs. The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.DOI
  11. [15]J. Filar and K. Vrieze. Competitive Markov Decision Processes. Springer, 1997.DOI
  12. [16]Eric A. Hansen, Daniel S. Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI), 2004.
  13. [17]Karel Horák and Branislav Bošanský. Solving partially observable stochastic games with public observations. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
  14. [18]Karel Horák, Branislav Bošanský, and Michal Pěchouček. Heuristic search value iteration for one-sided partially observable stochastic games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
  15. [19]Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning, 2002.
  16. [20]Dhruva Kartik and Ashutosh Nayyar. Zero-sum stochastic games with asymmetric information. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4061–4066, 2019. doi: 10.1109/CDC40024.2019.9030177.DOI
  17. [21]Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2):247–259, June 1996.DOI
  18. [22]Vojtěch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisý. Rethinking formal models of partially observable multiagent decision making. Artificial Intelligence, 303:103645, 2022. ISSN 0004-3702. doi: https://doi.org/10.1016/j.artint.2021.103645.
  19. [23]H. W. Kuhn. Extensive Games and the Problem of Information. Princeton University Press, Princeton, NJ, 1953.
  20. [24]Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 7187–7194, 2020.arxiv.org/abs/1912.02318
  21. [25]Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael B. Johanson, and Michael H. Bowling. Deepstack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 356:508–513, 2017.
  22. [26]Rémi Munos. Error bounds for approximate policy iteration. In Tom Fawcett and Nina Mishra (eds.), Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), August 21-24, 2003, Washington, DC, USA, pp. 560–567. AAAI Press, 2003.
  23. [27]Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control, 58(7):1644–1658, 2013.arxiv.org/abs/1209.1695
  24. [28]T. Neller and Marc Lanctot. An introduction to counterfactual regret minimization. 2013.
  25. [29]J. von Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100:295–320, 1928.DOI
  26. [30]Frans Adriaan Oliehoek. Sufficient plan-time statistics for decentralized POMDPs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013.
  27. [33]Fabian Raoul Pieroth, Katherine Fitch, and Lenz Belzner. Detecting influence structures in multi-agent reinforcement learning. In Proceedings of the 41st International Conference on Machine Learning (ICML), pp. 40740–40761. PMLR, 2024.
  28. [34]Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. Point-based value iteration: An anytime algorithm for POMDPs. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), volume 3, pp. 1025–1032, 2003.
  29. [35]Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296–301, 1951. ISSN 0003486X, 19398980.
  30. [36]John Schulman, Sergey Levine, Philipp Moritz, Michael Jordan, and Pieter Abbeel. Trust region policy optimization. In Proceedings of the 32nd International Conference on Machine Learning - Volume 37, ICML’15, pp. 1889–1897. JMLR.org, 2015.arxiv.org/abs/1502.05477
  31. [37]John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017.arxiv.org/abs/1707.06347
  32. [38]Guy Shani, Joelle Pineau, and Robert Kaplow. A survey of point-based pomdp solvers. Autonomous Agents and Multi-Agent Systems, 27(1):1–51, 2013.DOI
  33. [39]L. S. Shapley. Stochastic games*. Proceedings of the National Academy of Sciences, 39(10):1095– 1100, 1953.
  34. [40]Richard D. Smallwood and Edward J. Sondik. The optimal control of partially observable Markov decision processes over a finite horizon. Operations Research, 21(5):1071–1088, 1973.DOI
  35. [41]Trey Smith and Reid G. Simmons. Heuristic search value iteration for POMDPs. In Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (UAI-2004), pp. 520–527. AUAI Press, 2004.arxiv.org/abs/1207.4166
  36. [42]Samuel Sokota, Ryan D’Orazio, Chun Kai Ling, David J. Wu, J. Zico Kolter, and Noam Brown. Abstracting imperfect information away from two-player zero-sum games. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp. 32169–32193, 2023.arxiv.org/abs/2301.09159
  37. [43]Edward J. Sondik. The optimal control of partially observable Markov decision processes over the infinite horizon: Discounted cost. Operations Research, 12:282–304, 1978.DOI
  38. [44]Oskari Tammelin. Solving large imperfect information games using CFR+. CoRR, 2014.arxiv.org/abs/1407.5042
  39. [45]Elise Van der Pol and Frans A. Oliehoek. Coordinated deep reinforcement learners for traffic light control. In NeurIPS Workshop on Learning, Inference and Control of Multi-Agent Systems, 2016.
  40. [46]Hua Wei, Chacha Chen, Guanjie Zheng, Kan Wu, Vikash Gayah, Kai Xu, and Zhenhui Li. Presslight: Learning max pressure control to coordinate traffic signals in arterial network. Pro- ceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1290–1298, 2019.
  41. [47]Auke J. Wiggers, Frans A. Oliehoek, and Diederik M. Roijers. Structure in the value function of two-player zero-sum games of incomplete information. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI), 2016.
  42. [48]Chao Yu, Akash Velu, Eugene Vinitsky, Jiaxuan Gao, Yu Wang, Alexandre Bayen, and Yi Wu. The surprising effectiveness of ppo in cooperative multi-agent games. Advances in neural information processing systems, 35:24611–24624, 2022.arxiv.org/abs/2103.01955
  43. [49]Yifan Zhong, Jakub Grudzien Kuba, Xidong Feng, Siyi Hu, Jiaming Ji, and Yaodong Yang. Heterogeneous-agent reinforcement learning. J. Mach. Learn. Res., 25(1), January 2024. ISSN 1532-4435.arxiv.org/abs/2304.09870
  44. [50]Martin A. Zinkevich, Michael Bradley Johanson, Michael Bowling, and Carmelo Piccione. Regret minimization in games with incomplete information. In Neural Information Processing Systems, 2007.DOI

Paper details

vlnc:W_5efkdxz6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents