The Update-Equivalence Framework for Decision-Time Planning
Authors: Samuel Sokota
Gabriele Farina
David J Wu
Hengyuan Hu
Kevin A. Wang
J Zico Kolter
Noam Brown
Venue: ICLR 2024 poster (2024)
Keywords: imperfect-information games
search
decision-time planning
Primary area: reinforcement learning
TL;DR: A framework for search in imperfect-information games based on update equivalences

Abstract: The process of revising (or constructing) a policy at execution time---known as decision-time planning---has been key to achieving superhuman performance in perfect-information games like chess and Go. A recent line of work has extended decision-time planning to imperfect-information games, leading to superhuman performance in poker. However, these methods involve solving subgames whose sizes grow quickly in the amount of non-public information, making them unhelpful when the amount of non-public information is large.
Motivated by this issue, we introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. In this update-equivalence framework, decision-time planning algorithms replicate the updates of last-iterate algorithms, which need not rely on public information. This facilitates scalability to games with large amounts of non-public information. Using this framework, we derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent. We validate the performance of these algorithms in cooperative and adversarial domains, notably in Hanabi, the standard benchmark for search in fully cooperative imperfect-information games. Here, our mirror descent approach exceeds or matches the performance of public information-based search while using two orders of magnitude less search time. This is the first instance of a non-public-information-based algorithm outperforming public-information-based approaches in a domain they have historically dominated.

Published as a conference paper at ICLR 2024
THE UPDATE-EQUIVALENCE FRAMEWORK FOR TIME PLANNING
Samuel Sokota Gabriele Farina
David J. Wut
Hengyuan Hu Kevin A. Wang
J. Zico Kolter
Noam Brown 16
Work done at Meta Al 'Carnegie Mellon University
Massachusetts Institute of Technology OpenAA
Stanford University "Brown University Bosch Al
ssokota@andrew edu gfarina@mit.edu
ABSTRACT
The process of revising (or constructing) policy execution time known as decision-time planning- has been key to achieving superhuman performance in perfect-information games like chess and Go. A recent line of work has extended decision-time planning to impeeffett-information games, leading to superhuman performance poker. However, these methods involve solving subgames whose sizes grow quickly in the amount of non-public information, making them unhelp- ful when the amount of non-public information is large. Motivated by this issue, we introduce alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. In this update- sillatte-euvvveence framework, decision-time planning algorithms replicate the updates of last-iterate algorithms, which need not rely on public information. This facilitates scalability to games with large amounts of non-public information. Using this framework. we derive provably sound search algorithm for fully cooperative games based on mirror descent and search algorithm for adversarial games based on magnetic mirror descent. We validate the performance of these algorithms in cooperative and adversarial domains, notably in Hanabi, the standard benchmark for search in fully cooperative imperfect-informatie approach exceeds or matches the performance of public information-be while using two orders of magnitude less search time. This is the first instance of a non- aublic-information approaches domain they have historically dominated.
games. Here, our mirror descent search
algorithm outperforming gublic-informan based
INTRODUCTION
Decision-time planning (DTP) is the process of revising (or even constructing from scratch) a policy immediately before using that policy to make a decision. In settings involving strategic decision making, the benefits of DTP can be quite large. For example, while decision-time planning ap- proaches have achieved superhuman performance in chess (Campbell et al., 2002), Go (Silver et al., 2016), and poker (Moravčík al. 2017 Brown and Sandholm 2018 2019), approaches without decision-time planning remain non-competiiive.
Currently, the dominant paradigm for DTP based on solving (or improving the policy much as possible in) subgames. In perfect-information games, the subgame at a state is naturally defined as game beginning from that state that proceeds according the rules as the original game. In contrast, the definition of subgame is nuanced in imperfect--nffommatin
games, due to the presence
of private information. While multiple definitions have been proposed, all those that facilitate sound
guarantees (Nayyar et al.] [013]] Dibangoye et al. 2013) Oliehoek 2013 Burch et al.
2014
Morav-
cik et al.] 2016; Brown and Sandholm 2017, Moravčík al.) 2017] Brown
2020 Sokota
al. 2023b) rely on variants of distribution known public belief state (PBS) 1
ie.. the joint
posterior over each player's decision point, given public information and the joint policy that has been played so far.
Note that different literatures use different names refer this distribution and its variants.

---

Published as a conference paper at ICLR 2024
planning has fundamental limitation: it is ineffective in settings with large amounts of non-public information. This shortcoming arises because PBS-based DTP dis- tributes its computational budget across all decision points supported by the PBS and because the number of such decision points increases with the amount of non-public information in the game. When the amount of non-public information is small, such as in Texas Hold'en em, where there only (2) 1326 possible private hands, this is non-issue because it is feasible to construct strong policies for decision points supported by the PBS. However, as the amount of non-public informa- tion grows, meaningfully improving for all such decision points becomes increasingly inviable. For example, in games where the only public knowledge is the amount of time that has passed, PBS- based subgame solving requires reasoning about every decision point consistent with the time step. In the worst case-games with no public information at all-aBS PBS-basce subgame solving requires solving the entire game, defeating the entire purpose of DTP.
Unfortunately,
In this work, motivated by the insufficiency of PBS- based conceptualizations, we investigate an al- ternative perspective on DTP that we call the viewing DTP algorithms as solving subgames, the -uulatee-quvvaeencee framework views them as im- plementing the updates of last-iterute algorithms- term that we use to refer to algorithms whose last iterates possess desirable properties, such monotonic improvements in expected return, de- creases in exploitability, or convergence to an equilibrium point This framework offers a simple mechanism for generating and analyzing principled DTP algorithms, contrasting rithms and analyses, which are notorious, especially in adversarial games, for their reconditeness. Furthermore, importantly, because these last-iterate algorithms need not involve PBSs, the update- equivalence framework for DTP is not inherently limited by the amount of non-public information. Indeed, the most natural instances of the framework focus their entire computation budget on the de- cision point that is actually occupied by the planning agent, entirely ignoring counterfactual decision points supported by the PBS.
framework for DTP. Rather than
algo-
We invoke the update-equivalence framework to derive DTP algorithm based on mirror descent (Nemirovsky and Yudin 1983; Beck and Teboulle 2003). We prove that this algorithm, which we call mirror descent search (MDS), guarantees policy improvement in fully cooperative games. We test MDS in Hanabi (Bard al., (020). the standard benchmark for search in fully cooperative imperfect-infornation games. Remarkably, MDS exceeds or matches the performance of state-of- the-art PBS methods while using two orders of magnitude less search time. This is the first instance of a non-public-informaation infformation-basee algoritim outperforming in a setting they' 've historically dominated. Furthermore, we show that the performance gap between MDS and PBS methods widens the amount of non-public information increases, reflecting MDS's s superior scalability properties. In addition to MDS, we also introduce a search algorithm for adver- sarial settings based on magnetic mirror descent (MMD) (Sokota et al.) 2023a) that we call MMD search (MMDS). We show empirically that MMDS significantly improves performance in games where PBS methods are essentially inapplicable due to the large amount of non-public information.
based approaches
2 BACKGROUND AND NOTATION
We use the formalism of finite-horizon partially observable stochastic games, or POSGs, for short (Hansen et al.) 2004). POSGs are a class of games equivalent to perfect-recall timeable extensive- form games (Jakobsen et al.] 2016; Kovarík et al., 2022). To describe finite-horizon POSGs, we use E S to notate Markov states, i's observations, h; E H.; notate joint actions, h E H = x dlll to notate histories, R, S x A + R to notate player i's reward function, T: A + ASS) to notate the transition function, O observation function.
E A, to notate player i's actions, o: E O; to notate player (,, (O, A,)" O, to notate i's decision points, a E A X, to
+ O; to notate player i's
Each player interacts with the game via a policy म,, which maps decision points to distributions over actions :.: H., + A(A)). Given joint policy x (m.).. we use the notation Px to notate
Forr example, this definition of last-iterate algorithm would include policy iteration in Markov decision processes, since its last iterate converges to the optimal policy, but exclude algorithms for games possessing only average-iterat guarantees, such as counterfactual regret minimization (Zinkevich et al. 2007) and fictitious play (Brown 1951.
2

---

Published as a conference paper at ICLR 2024
probability functions associated with the joint policy For example, Px h4) denotes the probability of history under joint policy т given that player occupies decision point h4-
The objective of player i is to maximize its expected return [+( [G] where the return is de- fined as the sum of rewards G := Σ, R, A4") and where we use capital letters to denote random variables. (We maintain the convention of using capital letters for random variables throughout the paper.) If the return for each player is the same, we say the game is common payoff. If there are two players and the returns of these players are the opposite of one another, we say the game is two player zero sum (2p0s).
We notate the expected value for an agent at history h under joint policy
2 (h') = E. G [r]
B.
Σ R.(SS A²)) h2 e'2x
The expected action value for an agent a history h" taking action af under joint policy denoted q. (h' a²) E- hh,, af E [R,(S", A²) + of (H+*2) ht,af]]
The expected value of a decision point h is the weighted sum of history values, where each history is weighted by its probability, conditioned on the decision point and historical joint policy vf (ht) Er [u (H))) h-]. Similarly, the expected action value for action ot at a decision point hę is defined Ex 1o7 [H7 ,d)) kg].
as of (hi,
3 THE FRAMEWORK OF UPDATE EQUIVALENCE
The framework of update equivalence rests on the idea that last-iterate algorithms and DTP algo- rithms may viewed, implicitly or explicitly, as inducing updates. For last-iterate algorithms, this induced update refers to the mapping from one iterate (i.e., policy) to the next. For DTP algorithms, this induced update refers to the mapping from the policy to be revised (called the blueprint policy) to the policy produced by the search. We define the idea that these updates may be equivalent below.
Definition 3.1 (Update equivalence). For some fixed game, decision deeision-timme planning algorithm and a last-iterate algorithm are update equivalent if, for any policy x' and any information state h4, the distribution of actions played by the decision-time planning algorithm at h; with blueprint n² is equal to the distribution of actions the last-iterate algorithm would play at h2 on iteration f 2++ given that it had played x' on iteration t.
There are at least two benefits to considering uodate-equivalence relationships for decision-tin time planning. First, it begets approach to analyzing DTP algorithms via their last-iterate algorithm counterparts. This avenue of analysis simply requires determining whether the next iterate is im- proved from the previous, circumventing host of complications that make the analysis of PBS approaches nuanced. Second, and perhaps more importantly, it enables the generation of new prin- cipled DTP algorithms via last-iterate algorithms with desirable guarantees.
We illustrate these benefits in the two coming subsections. In Section 3.1 we focus on last-iterate algorithms that operate using action-value feedback, providing a general procedure generate DTP analogues of these algorithms and discussing three DTP algorithms constructed via this procedure, as well as their soundness. In Section 3.22 we also discuss last-iterate algorithms that do not operate using action-value feedback, demonstrating how the framework of update equivalence can be used to generate or justify DTP algorithms with more complex structure.
3.1 ACTION- ACTION-VALUE-BEE
PLANNERS
In Algorithm [] give procedure for constructing DTP algorithms that update-equivaleds to last-iterate algorithms operating on action-value feedback. Specifically, let the last-iterate algorithm be represented by continuous function WI (Tr(), 9" (hx)) + nh (h,) mapping the current pol- icy n' to the next policy x²+1 by incorporating the action-value feedback qa for the current policy. Algorithm [ repeatedly samples histories starting from a given decision point and the joint policy and acquires estimates of the sample returns for these histories via rollouts. When the computational
3

---

Published as a conference paper at ICLR 2024
budget has been exhausted, A applies the update function U/ to the current joint policy and estimated action values. This leads to an
DTP algorithm, as we establish next.
Proposition 3.2. date function U is continuous. Then, as the number of rollouts goes to infinity, the output of Algo- rithm 1
Consider a last-iterate algorithm operating with action-value feedback whose up-
conditioned on U and given inputs hi n, converges in probability to (ol((((s)))) (hs), (ha))
Proof. This proposition holds because & converges in probability to q. (h.) by the law of large numbers and 4 is continuous.
Monte Carlo Search Algorithm I enables us to relate last-iterate algorithms with DTP counterparts. A notable existing instance of such a relationship had already been identified by [Teaauro (1995) and (Tesauro and Galperin (199)) between policy iteration (as the last- iterate algorithm) and Monte Carlo search (as the corresponding DTP algorithm). Indeed, by plugging policy iteration's 's local update func- tion into Algorithm[ we recover exactly Monte Carlo search special case. The local update induced by policy iteration can be written as arg max ,7) q):
Algorithm Update Equivalent Search for Algorithm with Action-Value Feedback and Update 4
Input: decision point Af. joint policy π Initialize [[a] as running mean tracker for a E A.
repeat
Sample history H' ~ P=(H' 1D)
for a A. do
Sample return G ~ Pe Pr (G2t H)
q[a| .upuued running mean (22) end for
until scarch budget is exhausted return ((x()))).))
U: (5,
#'EA(A.)
where म E (AA)) and q E |R In other words, policy iteration's update simply plays a greedy policy with respect to its action values. By Proposition 3.2 when the computational budget given to the Monte Carlo search DTP algorithm grows, the policies produced converge to those of policy iteration. So, with enough budget, Monte Carlo search inherits all desirable properties enjoyed by policy iteration, including convergence to optimal policies in single-agent settings and convergence to Nash equilibrium in perfect-inforrmaiinn 2p0s games (Littman 1996).
Mirror Descent Search Algorithm 1 also enables us give novel justification to DTPP approaches in settings in which giving guarantees has been historically difficult. One example of such as a set- ting is common-payoff payoff games, where naive application of Monte Carlo search can lead bad performance as a result of the posterior over histories induced by the search policy diverging too far from the blueprint policy's 's posterior (Sokota al., 2022). We show that this issue can be resolved using mirror descent (Beck and Teboulle| 2003) Nemirovsky and Yudin 1983). which is a general approach to optimizing objectives that penalizes the distance between iterates. In the context of se- quential decision making, a natural means of leveraging mirror descent is to instantiate simultaneous updaters U/ of the form
1 KL #) 7
U: (T, ②) + arg m . #'EA(A.)
at each decision point, where म is local policy, 17 is a stepsize, q is local action-value vector. In the case of discrete action spaces, this update reduces to the closed-form learning algorithm Ud 7) ", known in literature as hedge or multiplicatiie weights update.
In the appendix, we show that mirror descent satisfies the following improvement property.
Theorem 3.3. Consider a common- common-payoofi game. Let a' be a joint policy having positive probability on every action at every decision point. Then, if we run mirror descent at every decision point with action-vat value feedback, for any sufficiently small stepsize n > 0, J [(x++1)+ Z J(r"). Furthermore, this inequality is strict if x² r11 + n² (that is, if x² is not a local optimum).
We call mirror descent search (MDS) the DTP algorithm obtained by applying Algorithm | with mirror descent the last-iterate algorithm. By virtue of Proposition 3.2 as the computational budget increases, MDS inherits the improvement property of Theorem 3.3
Magnetic Mirror Descent Search Another example of a setting that has been historically dif- ficult for DTP is 2p0s games. In such settings, neither policy iteration- nor mirror descent-bases these approaches tend to cycle, diverge, even exhibit
approaches yield useful
4

---

Published as a conference paper at ICLR 2024
formally chaotic behavior already in simple games such as pack-pppr-sscissors (Cheung and Pil- touras. 2019). It was recently shown that this issue can be empirically and reliably resolved using magnetic mirror descent (Sokota et al. 2023a), which is an extension of mirror descent with addi- tional proximal regularization to magnet that dampens these cycles. As with mirror descent, in the context of sequential decision making, a natural means of leveraging magnetic mirror descent is to instantiate simultaneous updaters U at each decision point:
U: (कt, Q) + arg max ( -L [KL((t. F'EA(A))
where a a regularization temperature and p E (Aa)) is a local reference policy; in the case of discrete action spaces, this update reduces to the following closed form: ((T, ②) x [ 1to0.
We call magnetic mirror descent update equivalent search (MMDS) the DTP algorithm obtained by applying Algorithm [ with the particular choices of magnetic mirror descent the last-iterate algorithm. Once again from Proposition 3.2 we establish that if the observation of MMD's 's reliable last-iterate convergence equilibrium made by (Sokota et al. (2023a) holds, then MMDS leads to expected improvement in 2p0s games as the computational budget grows.
Stundamd
With Subgime Updites
With BPT
Opponent Lpdae
Kuhn Poker
2x2 Abrapt Dark Hox
4-Sided Liar's Dice
Ledoe Poker
10
10-3
KL. Divegennss
10 2
10-3
10-4
10
10-
0
2
8
10
2
4
6
8
10
2
6
8
10
Derratioss (Chousands)
Figure 1: Divergence to AQRE function of iterations for last-iterate algorithm analogues of variants of MMD-based search algorithms. Each variant exhibits empirical convergence.
3.2 BEYOND ACTION- VALUE-BEI -ESEED PLANNERS
Many DTP algorithms cannot be derived from Algorithm I that nevertheless may be useful to view from the perspective of update equivalence. One class of such approaches makes updates at fu- ture decision points during search. Approaches of this form, such as Monte Carlo tree search (MCTS) (Coulom) 2006; Kocsis and Szepesvári] 2006) [Browne et al. 2012), played an important role in successes in perfect information games (Silver et al. al. (2016 2018 Schrittwiseer et al. (2019): Antonogiou et al. (2022). Another class of approaches fine-tune the belief model (Sokota et al. 2022) to track the search policy.
We provide empirical evidence for the soundness of three such MMD-based approaches in the con- text of imperfect-inte innerfecttinformatiion 2p0s games: 1) With subgame updates, A variant in which the plan- ning agent also performs MMD updates at its own future decision points; 2) With belief fine- finnig (BFT), a variant that implements an MMD update on top of a posterior fine-tuned the search policy; 3) With opponent updates, variant that implements an MMD update assuming subgame joint policy which the opponent has performed an MMD update at its next decision point. See Appendix B. for further algorithmic details.
In Figure] I we measure the divergence of these last-iterate algorithm counterparts to agent quantal response equilibrium (AQRE) (McKelvey and Palfrey 1998) as function of the number of update iterations. We find that all three last-iterate algorithm analogues exhibit empirical convergence, suggesting that these DTP algorithms may be safe in 2p0s settings. More generally, these findings may hint that, so long as MMD is used as a local updater, one may have wide leeway in designing safe DTP algorithms for 2p0s games.
5

---

Published as a conference paper at ICLR 2024
4 EXPERIMENTS
In this section, we add fürther evidence for the update-equivalence framework's utility by showing that the novel DTP algorithms derived from it also perform well in practice. We focus on two settings with imperfect information: i) two variants of Hanabi (Bard et al.] (020). fully cooperative card game in which PBS- based DTP approaches are considered state-of ofete----t-- and ii) 3x3 Abrupt Dark Hex and Phantom Tic-Tac-Toe, 2p0s games with virtually no public information.
4.1 HANABI
We consider two versions of two-player Hanabi, a standard benchmark in the literature (Bard et al, 25 is considered winning. First,
2020). Both versions scored out of 25 points-scoring trained instances of PPO (Schulman et al.) 2017) in self play for each setting. We intentionally selected instances whose final performance roughly matched those of R2D2 (Kapturowski et al., 2019) instances that have been used to benchmark DTP algorithms. Next, we trained a belief model for each PPO policy using Seq2Seq with the same setup and hyperparameters as (Hu al.] (2021): in this setup, the belief model takes in the decision point of one player and predicts the private information of the other player. conditioned on the PPO policy having been played thus far.
We adapted our implementation of MDS from that of single-agent SPARTA with a learned belief model (Hu et al. (021). Our adaptation involves three important changes. First, MDS performs search for all agents, rather than only one agent, as was done in (Hu et al.) (021). Second, MDS plays the argmax) of a mirror descent update, rather than the argmax of the empirical Q-values from search, SPARTA does. Third, MDS always plays its search policy. This contrasts both SPARTA (Lerer et al. 2020| Hu et al. 202T) and RLSearch (Fickinger et al.] 202I), which, after doing search, perform a validation check to determine whether the search policy outperforms the blueprint policy: if the validation check fails, the blueprint policy is played instead of the search policy. This validation check can be expensive and usually fails (SPARTA and RLSearch only play their search policies on a handful of turns). Thus, MDS's s ability to sidestep the validation check is a significant advantage.
5-Card Hanabi We first test MDS in the 5-card 8-hint variant of Hanabi, which is commonly played by humans. Specifically, we compare MDS using a PPO blueprint policy against single- and multi-agent SPARTA and RLSearch, which are considered statc-of-the-arg with exact belief models and an R2D2 blueprint policy: we also compare against single-agent SPARTA using the same PPO blueprint policy and Seq2Seq belief model. For MDS, we use 10, 000 samples from the belief model for search; this takes about seconds per decision, which is about two orders of magnitude faster than multi-agent SPARTA and multi-agent RL-Search.
We report our results in Table [ To give context to the results, the strongest reported performance of model-free agents in literature exceeds 24.40, while that of the strongest reported search agents exceeds 24.60 (Hu et al., 202T). becomes increasingly hard to improve the performance as the score increases; for high-scoring policies, increases as small as few hundredths of points considered substantial and can translate to multiple percentage points in winning percentage. To Lettraation,nerreeeeer
give specific numbers an illustration, Lerer et al. (2200) report that improving the expected return from 24.53 to 24.61 can increase the winning percentage from 71.1% to 75.5%.
Despite being handicapped by 1) approximate belief model, 2) lack of validation, and 3) two ders of magnitude less search time, we find that MDS achieves superior or comparable performance to PBS methods. Given the historical dominance of PBS approaches in settings where they ap- plicable, the fact that a non-PBS-base method could achieve competitive performance is already notable: that MDS does so with such severe handicap is particularly impressive.
7-Card Hanabi We next investigate MDS in the 7-card 4-hint variant of Hanabi. This variant was introduced by Hu et al. (202T) to illustrate the challenges of performing search as the amount of private information scales. Specifically, the number of possible histories is too large to enumerate. As a result, multi-agent SPARTA inapplicable altogether, single-agent SPARTA and RLSearch require an approximate belief model, and multi-agent RI Rearecc requires both an approximate belief
Note that this differs slightly from our description in the previous section in that we are playing the argmax, rather than sampling, from the updated policy.

---

Published as a conference paper at ICLR 2024
Table I: MDS (bold) compared to SPARTA and RLSearch in 5-card 8-hint Hanabi. Despite us- ing approximate beliefs and roughly two orders of magnitude less search time, MDS matches the performance of prior methods using exact beliefs. Columns to the left of the divider used an R2D2 blueprint that scored 24.23=0.00 columns to the right used PPO blueprint that scored 24.24-1..0..
Search
SPARTA Single Exact V
RLSearch
SPARTA
RLSearch
SPARTA
MDS
Agents planned
Single Exact
Multi Exact
Multi Exact
Single Seq2Seq
Multi
Belief model
Seq2Seq
Validation used
X
Time per move
3s
35s
450s
180s
2s
Expected return Standard error
24.57 + 0.03
24.59
24.61
24.62
24.52 + 0.02
24.62 + 0.02
+ 0.02
0.02
+ 0.03
Table 2: MDS (bold) compared to SPARTA and RLSearch in 7-card 4-hint Hanabi; MDS compares favorably these approaches. Columns to the left of the divider used an R2D2 blueprint that scored 23.67 = 0.02; columns to the right used a PPO blueprint that scored 23.66 = 0.03.
Search
RLSearch Single Seq2Seq
RLSearch Single BFT V
RLSearch
SPARTA
MDS
Agents planned
Multi BFT
Single
Multi Seq2Seq
Belief model
Seq2Seq
Validation used
X
Time per move
100s
310s
Expected Return
24.14
24.18
24.18
24.17
24.2 + 0.02
Standard error
= 0.04 + 0.03
+ 0.03
+ 0.03
model and belief fine-tuning (Sokota et al. 2022). Because of the significantly increased burden of running PBS methods in this setting, one would hope that method that eschews PBSs might be able to outperform PBS methods. And, indeed, in Table 2 where we report expected return and standard error over 2000 games, find that MDS does outperform multi-agent RLSearch with BFT, as well as a variety of single-agent search techniques. These results support our claim that the update--quivalence framework offers superior scaling properties in the amount of non-public information, compared to PBS methods.
To offer further intuition for the behavior of MDS, we show the performance in 7-card 4- hint Hanabi a function of mirror descent's stepsize in Figure 2 As might be expected, we find that improvement is unimodal function of stepsize: If the stepsize is too small, oppor- tunities to improve the blueprint policy are ne- glected; on the other hand, if the stepsize is too large, the search policy's posterior diverges too far from that of the blueprint for the search to provide useful feedback.
24.25
Expected Return
23.75
23.50
Blueprint (7-card 4-hint)
MDS (7-card 4-hint)
23.25
10-1
10
10a
102
Stepsize
Figure 2: Performance of MDS as a function of stepsize in 7-card 4-hint Hanabi. Small step sizes provide less improvement over the blueprint; overly large step sizes cause the search policy to diverge too far from the blueprint, resulting in less improvement even detriment.
4.2 3x3 ABRUPT
DARK HEX AND PHANTOM TIC-TAC-TO
Unlike cammon-payoff games, measuring per- formance 2p0s games difficult because the usual metric of interest-exe sidersst-exploitaabiity (i.e., the expected return of best responder) cannot be cheaply estimated. Indeed, providing reasonable lower bound requires training an approximate best response (Timbers et al. 2022), which may costly. To facilitate this approximate best re- sponse training under modest computation budget, we focus experiments that selects actions uniformly at random at every decision point so that rollouts may performed quickly; furthermore, rather than using a learned belief model, track approximate posterior using particle filtering (Doucet and Johansen, 2009) with particles. If particles remain, our im- plementation of MMDS performs rollout for each particle for each legal action until the end of the
blueprint policy

---

Published as a conference paper at ICLR 2024
Approach
MMDOM
MMDI MMDS
Approsch
Rondom
Mandom-MMMS
3x3 Abbuuee Dark Hex
Plantou Tie- Toe-Toe
3x3 Abrupt Dark Hex
Phanoon The Tac: Toe
0.6
0.6
Expected Reuurn
Eipeted Ratam
02-
01
.44
tatogl Antion
Rmaoer
Protzaar
Ararritt
AFarcinn ANMIVAS
AD422100))
Antiot
Resiom
FReKIM)
Is Lagal Artion
Rasdon
LP
Prociom)
ApsPPt
NPSP ()M)
MBDD (M)
(9M)
Is Legal Autros
Randow
IMD
NESI (M))
hrssy MIME
(ON))
Opponent
Opponent
(a) Random with MMDS
(b) MMD(IM) with MMDS
Figure 3: Expected return of uniform random and uniform random blueprint MMDS (left) and MMD(IM) and MMD(IM) blueprint + MMDS (right) versus various opponents 3x3 Abrupt Dark Hex and Phantom Tic-Tac-Toe. MMDS tends to improve head-to-head expected return.
game and performs an MMD update on top of the empirical means of the returns. Otherwise, the agent executes the blueprint policy.
We empirically investigate MMDS in 3x3 Abrupt Dark Hex and Phantom Tic- Tic-Tac-Tor Toe, two standard benchmarks available OpenSpiel (Lanctot et al. 2019). We show approximate exploitability results in Table 3 We computed these results using OpenSpiel's (Lanctot et al.) (019) DQN (Mnih)
al., 2015) best response code, trained for 10 million time steps. We show standard error over 5 DQN best response training seeds and 2000 final evaluation games for the fully trained model. We compare against a bot that plays the first legal action, the uniform random blueprint, Liang et al. (2018)'s implementation of independent PPO (Schulman al. (017)). Lanctot al. (2019)s implementation of NFSP (Heinrich and Silver 2016). and MMD (Sokota et al.) 2023a). For the learning agents, ran 5 seeds and include checkpoints trained for both I and 10 million time steps.
We find that MMDS reduces the approximate exploitability of the uniform random blueprint by more than a third, despite using a meager 10-particle approximate posterior. Furthermore, MMDS achieves lower approximate exploitability than all non- MMD-based approaches.
Table 3: Approximate exploitability in 3x3 Abrupt Dark Hex and Phantom Tic-Tac- Toe, 0 to 100 scale. MMDS (bold) substan- tially reduces Random's exploitability.
Agent
3x3 Ab. DH
Phantom TTT
1st Legal Action
100 0
100 0
We also investigate the performance of MMDS in head-to-head matchups. We show results us- ing the uniform random blueprint with 10 parti- cles and also MMD(IM) blueprint with 100 par- ticles in Figure 3 The values shown are aver- ages over 10,000 games with bootstrap estimates of 95% confidence intervals. We find that MMDS tends to improve the performance of the blueprint policies in both cases, despite the short length of the games.
Random
78 +
PPO(IM steps)
6
PPO( IOM steps)
100 =
9
NFSP( IM steps)
95
NFM steps)
78
Random+MMDS
50 10
50
MMD steps)
34
37+11
MMD(10M steps)
20
15
RELATED WORK
Other Approaches to Imperfect Information Motivated by the deficiencies of PBS-based DTP described above, a small group of existing works has advocated for alternative approaches to DTP for commonn-payof" games (Tian et al., 2020) and 2p0s games (Zhang and Sandholm, 1021). Tian et al. (2020)* s approach relies on a result that shows that it is possible to decompose the change in expected return for two different joint policies across decision points. By leveraging this result, Tian et al. (2020) introduce a search procedure called joint policy search (JPS) that is guaranteed to not decrease the expected return. Zhang and Sandholm (2021)'s approach is based on the insight
8

---

Published as a conference paper at ICLR 2024
that, in practice, it is effective consider subgame that excludes most of the decision points supported by the PBS. Specifically, Zhang and Sandholm (2021) advocate in favor of solving a maxmargin subgame (Moravcik et al. 2016) that includes the planning agent's 's true decision point, as well as any opponent decision points that are possible from the perspective of the planning agent. Despite proving the existence of games in which this approach, which they call 1 1-KI.SS, increases the exploitability of the policy, iZhang and Sandholm (2021) find experimentally that, on small and medium-sized games, I-KLSS reliably decreases exploitability. In concurrent work. Liu et al. (2023) derive an alternative variant of 1-KLSS that guarantees safety, making it promising approach for scaling search to adversarial settings with large amounts of non-public information.
Structurally Similar Approaches While the motivation for the equivalequiv framework
most closely resembles of the works of TTan et al. (2020) and /Zhang and Sandholm (2021), 1), nat- ural instances of the update-equivalence framework are structurally more similar to search algo- rithms unrelated to resolving issues with PBS-based planning. As discussed previously, arguably the most fundamental instance of the framework of update equivalence is Monte Carlo search (MCS) TTsaauro 1995| Tesauro and Galperin 1996), which is update equivalent to policy iteration, as was articulated by Tesauro and Galperin| (996) themselves: "[MCS] basically implements a single step of policy iteration." " More recently. Anthony et al.] (2019); [Anthony| (202T); Hamrick et al. (202 I);
Lerer al. (2020); Hu et al.] (2021) investigate MCS in variety of settings: Anthony et al. (2019) and Anthony (2021 I find that it yields perhaps surprisingly good performance relative to MCTS in Hex; Lex:/hariick et al. (2021) report comparable performance with MCTS across a variety of settings,
with the exception of Go; Lerer et al. (2020) and Hu et al. (202I) show strong results for Hanabi (under the names single-agent SPARTA and learned belief search).
In his work. Anthony (202T) also investigates a search algorithm called policy gradient search that performs policy gradient updates at future decision points. He finds that a variant of this approach that involves regularization toward the blueprint policy tends to outperform not regularizing. This approach is similar to some of the variants of MMDS investigated in Section 3.2 The combination of policy gradient search and the framework of update equivalence may be fruitful direction in the pursuit of algorithms that perform well in both perfect and imperfect information games.
Separately from Anthony (2021). Jacob et al. (2022) also investigate approaches to DTP involving regularization toward blueprint. Jacob et al. (2022) show empirically that, by performing regular- ized search, it is possible to increase the expected return of an imitation learned policy without a loss of prediction accuracy (for the policy being imitated). The most immediately related experiments to this work those concerning Hanabi, in which Jacob et al. (0022) investigated MDS (under the name piKI. SPARTA) applied on top of imitation learned blueprint policies. [Jacob et al. 2022) note that this approach reliably increases the performance of weak policies, but neither recognize that it possesses an improvement guarantee nor that it is simply performing a hedge update, as we do in this work. Pacob al. (2022)* experiments on Diplomacy (Paquette al. 2019) are also related in analogue of MMDS. This approach played an important role in recent empirical successes for Diplomacy (Bakhtin et al.] [023] Metal Fundamental AI Research Diplomacy Team (FAIR) et al. 2002), suggesting that the framework of update equivalence is natural approach to general-sum settings.
that their approach is similar to follow-the www.thhggllaiized-eeeaeeeeee
6 CONCLUSION AND FUTURE WORK
In this work, motivated by the deficiencies of search algorithms based on public belief state rep- resentation of cnperfect-informaatee planning, which we call the framework of update equivalence. We show how the framework of update equivalence can be used to generate and ground new decision-time planning algorithms for imperfect-informen
games, we advocate for a new paradigm for decision-ting time
games. Furthermore, we show that these algorithms can achieve competitive (or superior) performance compared with ofate-of-the-ant art PBS- methods in Hanabi and can reduce approximate exploitability in 3x3 Abrupt Dark Hex and Phantom Tic-Tac-Toe.
We believe the framework of update equivalence opens the door to many exciting possibilities for DTP and expert iteration (Amthony et al. 2017 Anthony] 2022 in settings with large amounts of im- perfect information. Among these are the prospects of extending algorithms resembling AlphaZero (Silver et al.) (018). Stochastic MuZero (Antonoglou et al. 2022), and Diplodocus (Bakhtin et al. 2023) to imperfecttinformaaeee games.

---

Published as a conference paper at ICLR 2024
7 ACKNOWLEDGEMENTS
We thank Brian Hu Zhang for helpful discussions regarding knowledge-limited subgame solv- ing (Zhang and Sandholm 2021 and Bugene Vinitsky for helpful feedback regarding the presenta- tion of the work.
REFERENCES
T. Anthony, Z. Tian, and D. Barber. Thinking fast and slow with deep learning and tree search. In Neural Information Processing Systems (NeurIPS), 2017.
T. Anthony, R. Nishihara, P. Moritz, T. Salimans, and J. Schulman. Policy gradient search: Online planning and expert iteration without search trees. Computing Research Repository (CoRR), 2019.
T. W. Anthony. Expert iteration. PhD thesis, UCL (University College London), 2021.
I. Antonoglou, J. Schrittwieser, S. Ozair, T. K. Hubert, and D. Silver. Planning in stochastic environ- ments with a learned model. In International Conference on Learning Representations (ICLR), 2022.
A. Bakhtin, D. J. Wu, A. Lerer, J. Gray, A. P. Jacob, G. Farina, A. H. Miller, and N. Brown. Master- ing the game of No-Press Diplomacy via -ugua-regulariieed reinforcement learning and planning. In International Conference on Learning Representations (ICLR), 2023.
N. Bard, J. N. Foerster, S. Chandar, N. Burch, M. Lanctot, H. F. Song, E. Parisotto, V. Dumoulin, S. Moitra, E. Hughes, Dunning, S. Mourad, H. Larochelle, M. G. Bellemare, and M. Bowling. The hanabi challenge: A new frontier for ai research. Artificial Intelligence, 2020.
A. Beck and M. Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 2003.
G. W. Brown. Iterative solution of games by fictitious play. In Activity Analysis of Production and Allocation. 1951.
N. Brown and T. Sandholm. Safe and nested subgame solving for imperfecttinnformation games. In Neural Information Processing Systems (NeurIPS), 2017.
N. Brown and T. Sandholm. Superhuman AI for heads-up no-limit poker: Libratus beats top profes- sionals. Science, 2018
N. Brown and Sandholm. Superhuman Al for multiplayer poker. Science, 2019.
N. Brown, A. Bakhtin, A. Lerer, and Q Gong. Combining deep reinforcement learning and search for imperfect-information games. Neural Information Processing Systems (NeurIPS), 2020.
C. B. Browne, E. Powley, D. Whitehouse, S. M. Lucas, P. I. Cowling, P. Rohlfshagen, S. Tavener, D. Perez, S. Samothrakis, and Colton. survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in Games, 2012.
N. Burch, M. Johanson, and M. Bowling. Solving imperfect information games using decomposi- tion. In AAAI Conference on Artificial Intelligence (AAAI), 2014.
M. Campbell, A. Hoane, and hsiung Hsu. Deep Blue. Artificial Intelligence, 2002.
Y. K. Cheung and G. Piliouras. Vortices instead of equilibria minmax optimization: Chaos and butterfly effects of online learning in zero-sum games. In Conference on Learning Theory (COLT), 2019.
R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games, 2006.
J. S. Dibangoye, C. Amato, O. Buffet, and F. Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. In International Joint Conference on Artificial Intelligence (ICCAI), 2013.
10

---

Published as a conference paper at ICLR 2024
A. Doucet and A. Johansen. A tutorial particle filtering and smoothing: Fifteen years later. Handbook of Nonlinear Filtering, 2009.
A. Fickinger, H. Hu, B. Amos, S. Russell, and N. Brown. Scalable online planning via reinforcement learning fine-tuning tuning. In Neural Information Processing Systems (NeurIPS), 2021.
J. B. Hamrick, A. L. Friesen, F. Behbahani, A. Guez, F. Viola, S. Witherspoon, T. Anthony, L. H. Buesing, P. Veličković, and T. Weber. On the role of planning in model-based deep reinforcement learning. In International Conference Learning Reprexentations (ICLR), 2021.
E. A. Hansen, D. S. Bernstein, and S. Zilberstein. Dynamic programming for partially observable stochastic games. In AAAI Conference on Artificial Intelligence (AAAT), 2004.
J. Heinrich and D. Silver. Deep reinforcement learning from self-play in imperfect-inforration games. Computing Research Repository (CoRR), 2016.
H. Hu, A. Lerer, N. Brown, and J. N. Foerster. Learned belief search: Efficiently improving policies in partially observable settings. Computing Research Repository ( (CoRR), 2021.
A. P. Jacob, J. J. Wu, G. Farina, A. Lerer, H. Hu, A. Bakhtin, J. Andreas, and N. Brown. Modeling strong and human-like gameplay with Kl.-regularized search. International Conference on Machine Learning (ICMI.), 2022.
Jakobsen, T. Sørensen, and Conitzer. Timeability of extensive-form games. In Innova- tions in Theoretical Computer Science (ITCS), 2016.
Kapturowski, G. Ostrovski, W. Dabney, Quan, and R. Munos. Recurrent experience replay in distributed reinforcement learning. In International Conference Learning Representations (ICLR), 2019.
L. Koesis and C. Szepesvári. Bandit based monte-carlo planning. In European Conference Machine Learning (ECML), 2006.
V. Kovarík, M. Schmid, N. Burch, M. Bowling, and V. Lisy. Rethinking formal models of partially observable multiagent decision making. Artificial Intelligence, 2022.
M. Lanctot, E. Lockhart, J.-B. Lespiau, V. Zambaldi, S. Upadhyay, J. Pérolat, S. Srinivasan, F. Timbers, K. Tuyls, S. Omidshafiei, D. Hennes, D. Morrill, P. Muller, T. Ewalds, R. Faulkner, Kramár, B. D. Vylder, B. Saeta, Bradbury, D. Ding, S. Borgeaud, M. Lai, Schrittiisser, T. Anthony, E. Hughes, Danihelka, and J. Ryan-Davis. OpenSpiel: A framework for reinforce- ment learning games. Computing Research Repository (CoRR), 2019.
A. Lerer, H. Hu, J. Foerster, and N. Brown. Improving policies via search in cooperative partially observable games. In AAAI Conference on Artificial Intelligence (AAAI), 2020.
E. Liang. R. Liaw, R. Nishihara, P. Moritz, R. Fox, K. Goldberg, J. Gonzalez, M. Jordan, and Stoica. RLlib: Abstractions for distributed reinforcement learning. In International Conference on Machine Learning (ICML), 2018.
M. L. Littman. Algorithms for Sequential Decision Making, PhD thesis, Brown University, 1996.
W. Liu, H. Fu, Q. Fu, and Y. Wei. Opponent-limited online search for imperfect information games. In International Conference on Machine Learning (ICML), 2023.
R. D. McKelvey and T. R. Palfrey. Quantal response equilibria for extensive form games. Experi- mental Economics, 1998.
Meta Fundamental AI Research Diplomacy Team (FAIR), A. Bakhtin, N. Brown, E. Dinan, G. Fa- rina, C. Flaherty, D. Fried, A. Goff, J. Gray, H. Hu, A. P. Jacob, M. Komeili, K. Konath, M. Kwon, A. Lerer, M. Lewis, A. H. Miller, S. Mitts, A. Renduchintala. S. Roller, D. Rowe, W. Shi, J. Spisak, A. Wei, D. Wu. H. Zhang, and M. Zijlstra. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science, 2022.
11

---

Published as a conference paper at ICLR 2024
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis. Human-level control through deep reinforce- ment learning. Nature, 2015.
M. Moravcik, M. Schmid, K. Ha, M. Hladik, and S. J. Gaukrodger. Refining subgames in large imperfect information games. In AAAI Conference on Artificial Intelligence (AAAI), 2016.
M. Moravčík, M. Schmid, N. Burch, Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johan- son, and M. Bowling. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science, 2017.
A. Nayyar, A. Mahajan, and D. Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions Automatic Control, 2013.
A. Nemirovsky and D. Yudin. Problem Complexity and Method Efficiency in Optimization. 1983.
A. Oliehoek. Sufficient plan-time statistics for decentralized pomdps. In International Joint Conference on Artificial Intelligence (IJCAI), 2013.
P. Paquette, Y. Lu, S. S. Bocco, M. Smith, S. O-G, J. K. Kummerfeld, J. Pineau, S. Singh, and A. C. Courville. No-press diplomacy: Modeling multi aulti- gameplay. Neural Information Processing Systems (NeurlPS), 2019.
J. Perolat, R. Munos, J.-B. Lespiau, S. Omidshafiei, M. Rowland, P. Ortega, N. Burch, T. Anthony, D. Balduzzi, B. De Vylder, G. Piliouras, M. Lanctot, and K. Tuyls. From Poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In Interna- tional Conference on Machine Learning (ICML), 2021.
J. Schrittwieser, 1. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lockhart, D. Hassabis, T. Graepel, T. Lillicrap, and D. Silver. Mastering atari, Go, chess and shogi by planning with a learned model. Nature, 2019.
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. Computing Research Repository (CoRR), 2017.
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, Schrittwieser, I. Antonoglou, V. Panncershellamm, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbren- ner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 2016.
D. Silver, T. Hubert, Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Ku- maran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 2018
Sokota, H. Hu, D. Wu, J. Kolter, N. Foerster, and N. Brown. A fine-tuning approach to belief state modeling. In International Conference on Learning Representations (ICLR), 2022.
S. Sokota, R. D'Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero- sum games. In International Conference Learning Representations (ICLR). 2023a.
S. Sokota, R. D'Orazio, C. K. Ling, D. J. Wu, J. Z. Kolter, and N. Brown Abstracting imperfect information away from two-player zero-sum games. In International Conference on Machine Learning (ICML), 2023b.
G. Tesauro. Temporal difference learning and -0-mammmnn... Journal of the International Computer Games Association (ICGA), 1995.
G. Tesauro and G. Galperin. On-line policy improvement using monte-carlo search. In Neural Information Processing Systems (NIPS), 1996.
Y. Tian, Q. Gong, and T. Jiang. Joint policy search for multi-agent collaboration with imperfect information. In Neural Information Processing Systems (NeurIPS). 2020.
12

---

Published as a conference paper at ICLR 2024
F. Timbers, N. Bard, E. Lockhart, M. Lanctot, M. Schmid, N. Burch, J. Schrittwieser, T. Hubert, and M. Bowling. Approximate exploitability: Learning best response. In International Joint Conference on Artificial Intelligence (ICCAI), 2022.
B. Zhang and T. Sandholm. Subgame solving without common knowledge. In Neural Information Processing Systems (NeurIPS), 2021.
M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Neural Information Processing Systems (NIPS), 2007.
13

---

Published as a conference paper at ICLR 2024
A THEORY
In this section, we prove Theorem 3.3 To start, consider the following more general lemma.
Lemma A.1 (Folklore). Let f E (2), where X S IRd is convex and compact, To E X, and xt be the solution the mirror descent step
= arg min (V(o)))) + (a) wEX
where 4 differentiable and 1-strongly convex with respect to norm enough, if xf + Z0.
||. Then, for n small
f(x < f(zo),
Proof.
From the finst-order necessary optimality conditions for the mirror descent step, we have
(zz)) Vp((**) - Vy(rro) - -xx) 2 V E X.
Hence, letting == Tu, and using the strong convexity of yo and the assumption that x * Eo. we obtain
- | mo < 0,
(V((z)), vo)
1)
and with a further application of the Cauchy- Cauchy-Schwarz inequality
|| xoll S V
By continuity of the gradient of f. there must exist > 0 such that
(VI(x), at mn) < 0 Va E B(xo,e).
Furthermore, the mean value theorem guarantees that f(x*) f(xo) = (VI(E), - xo)
for some & on the line connecting on to x+. So, as long as v/ v/[V][ <, we have
f(x < f(xo).
as we wanted to show.
Theorem 3.3 Consider a common-paye game. Let n" be a joint policy having positive probability on every action each decision point. Then, if we run mirror descent every decision point with action-value feedback, for any sufficiently small stepsize 17.
J( 2 J(T").
Furthermore, this inequality is strict 4 # n² (that is, if R is not local optimum).
Proof. The space of joint policies II Cartesian product of probability simplices, immediately implying that it is convex and compact. Furthermore, the expected return function is polynomial function of any joint policy æ Hence, J E CIT).. The result then follows directly from Lemma A.I as, by hypothesis, the players are performing mirrrr descent steps on J.
B EXPERIMENTS
In this section, we provide further details about some of our empirical results and also show some additional results.
B.1 BEYOND ACTION- VALUE-BASED PLANNERS
First, describe in greater detail the DTP algorithms that investigated in Section 3.2
14

---

Published as a conference paper at ICLR 2024
With Subgame Updates With subgame updates differs from MMDS in the feedback it uses. In particular, rather than using the action values for the current policy, with subgame updates uses the action-values for the joint policy induced by performing MMD updates at its own future decision points (but leaving the opponent's 's policy fixed). Because the opponent is fixed, in tabular settings, compute the feedback for the last-iterate algorithm analogue of this approach using one backward induction pass for each player.
With Belief Fine-Tuning With BFT differs from MMDS in the distribution it samples histories from. In particular, rather than sampling from the distribution induced by the current policy, samples from the distribution induced by the search policy for each player.
With Opponent Update With opponent update differs from MMDS in the feedback it uses. In particular, rather than using the action values for the current policy, with opponent update uses the action values for the joint policy induced by performing time step. Note that, as a DTP algorithm, this approach would involve two belief model sampling steps: one sample an opponent decision point for updating and one sample an unbiased history for that opponent information state.
MMD update for the opponent the next
Agent Quantal Response Equilibria Solving In Figure 4 we show the convergence results from the main body, along with the exploitabilities the corresponding iterates. For these experiments, we used 0.1 and = a/10, except for with opponent updates Leduc, where we used r = a/20,, and with subgame updates on Leduc, where we used 17 = a/50.
Standard
With Subgame Updates
With BFT
With Opponent Updattz
Kuhn Poker
2x2 Abrupt Dark Hex
4-Sided Liar's Dice
Leduc Poker
100
10-1
KL Diveraaoe
10-2
10
10
10
10-1
10
10
2
1
10
0
2
4
6
8
Iterations (thousands)
Stundard
With Subgame Updates
With BFT
With Opponent Update
2x2 Albrapt
Sided Liar's
Leduc
Exploisabiliy
K0
2
4
8
10
4
6
8
10
6
8
10
0
2
4
8
10
Iterations (thoasands)
Figure 4: Solving for agent quantal response equilibria using last-iterate algorithm analogues of variants of MMDS.
MiniMaxEnt Equilibrium Solving In Figure 5 we show convergence results for solving for MiniMaxEnt equilibria, which are the solutions of MiniMaxEnt objectives (Perolat et al. (021). A MiniMaxEnt objective an objective of the form
T: ग + Σ R. A') + - aH((
15

---

Published as a conference paper at ICLR 2024
We used 0.1 and 17 = a/10, except for with opponent update Ledue, where used a a22,, and with subgame updates on Leduc, which used r) = a/50. We again observe empirical convergence.
Standard
With Sulggame Updates
With BFT
With Opponent Update
Kubm Poker
2x2 Abrupt Dark Hex
4-Sided Liat's Dioe
Lodue Poker
10"
KL D.Deeggencs
1111
10-2
Ale
10-3
10
10-5
10
6
10
Iterations (thousands)
Standard
With Subgame Updates
With BFT
With Opponent Update
Kuhn Poker
2x2 Ahrupt Dark Hex
4.Sided Liar's Dice
Ledic Poker
Exploitahiiit
10
10
8
0
8
10
0
2
10
0
2
10
Berratinss (thousands)
Figure 5: Solving for MiniMaxEnt equilibria using last-iterate algorithm analogues of variants of MMDS.
Solving for Nash Equilibria Next show that these last-iterate algorithm analogues be made to converge to Nash equilibria by annealing the amount of regularization used. We show that these results in Figure compared against CFR (Zinkevich al. 2007). The hyperparameters for these results are shown in Table
Standard
With Subgame Updates
With BFT
With Opponent Update
CFR
Kuhh Poker
2x2 Abrupt Dark Hes
4-Sided Dice
Ledue Poker
105
Exploitabiiiy
10
10--4
10
10
10
10a
10P
10'
10
10*
Iterations
Figure 6: Exploitability of different MMDS analogues with annealed regularization.
16

---

Published as a conference paper at ICLR 2024
Method Game
Kuhn Poker
2x2 Abrupt
4-Sided Liar's Dice
Ledue Poker
Dark Hex
Standard
yr 7/e 2
5
1
V
Y
Y
y
With Subgame Updates
a₁ 1/e Vi
Ot T Y
0t
v7' 7)t 2
0x
L 7tt 3YT
With BFT
ag π Y
at 12t Y
a
VI 1) V7
S 9t 2/r
With Opponent Update
a2 = 1/e =
vi
Oç 7rt = Vi
a₁ N/e = V7
02 VE 7t 2V8
Table 4: Schedules for Figure
Solving for Nash Equilibria with MiniMaxEntRL objectives We also show analogous results for MiniMaxEnt objectives in Figure The hyperparameters for these experiments are shown in
5
Standard
Subgame Updates
Opponeni Update
Kuhn Paker
2x2 Abrupt Dark Hex
4-Sided Liar's Dice
Leduc Poker
10
Expleitabilla
10
10-2
10-3
10
10a
10
10a
102
101
102
101
10'
Figure 7: Exploitability of different MMDS analogues under MiniMaxEnt objjetiven objectives with annealed
regularization.
Method' Game
Kuhn Poker
2x2 Abrupt Dark Hex
4-Sided Liar's Dice
Ledue Poker
One-Step Search
Og ?) 7
at 1)
YI
72: fl
Y
at
Multi-Step Search
Oe = V7
0r = VT
Ot v7 T/t
2/7
v7. 5v
BFT Search
Og 47
a; 1 YI
Vi: Vi
1
87 9) Y
Opponent Search
Ore f) V7
Or l]t VT
0t 1t Vi
O2 v 1)t 2V7
Table 5: Schedules for Figure
B.2 HANABI
For our Hanabi experiments, we used 20 for the MDS results in Tables and 2 search with 10,000 samples.
We performed
B.3
3x3 ABRUPT DARK HEX AND PHANTOM-TIC-TTE -AC---AC-TEE
For our 3x3 Abrupt Dark Hex and Phantom-Tic-Tac- Tore- experiments with uniform blueprint, we used 77 50. a 0.01, and set p to be uniform. For the MMD(IM) blueprint, used 17 10, = 0.05, and set p to be uniform. For particle filtering, we sampled 10 particles for the uniform blueprint and 100 particles for the MMD(IM) blueprint from the start of the game independently at every decision point to reduce bias. For the baselines, we used the same setup as Sokota et al. 2023a
17


Reviews:
[{"review_id": "FmwSjLEeUR", "reviewer": "Reviewer_kQSj", "summary": "The paper studies decision-time planning (DTP) which is crucial in achieving superhuman performance in games, especially in imperfect-information games. The authors introduce the concept of update equivalence, a new framework for DTP that replicates the updates of global policy learners. This approach allows for sound and effective decision-time planning in games with extensive non-public information. The authors propose two DTP algorithms, mirror descent update equivalent search (MD-UES) and magnetic mirror descent update equivalent search (MMD-UES), and evaluate their performance in various games.", "questions": "How does the proposed framework of update equivalence fundamentally differ from the traditional subgame-based approach in DTP? Can authors put the differences or advantages into several points so that the ideas are clear?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of the notion of update equivalence is novel, which is not constrained by the amount of non-public information, making it applicable to a wider range of imperfect-information games.\n2. The proposed algorithm  presents competitive or superior results compared to state-of-the-art subgame-based methods while requiring significantly less search time.", "weaknesses": "1. The requirement that algorithm needs to exhaust all the search budget seems inefficient and the performance highly depends on this computational costs.\n2. I would prefer a separate \"related works\" section to make the presentation more clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QJl6HSw7gE", "reviewer": "Reviewer_ipeG", "summary": "This paper studies the decision-time planning problem with imperfect information by relating it to global policy learners. It introduce an update equivalence framework, based on which two algorithms are proposed to turn global policy learners to decision time planners. Experiments on games validate the promising performances of the proposed algorithms.", "questions": "- Does Proposition 3.2 rely on the definition of global policy learner operating with action-value feedback?\n- How to guarantee the desired connection between $\\mathcal{U}^{global}$ and $\\mathcal{U}^{global}_Q$ exist, and if so, how to obtain the corresponding function?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "+ Gaming with imperfect information is a challenging problem, and this work provides an approach that is different from the conventional Public Belief State (PBS)-based planning.\n+ The experiment results seem promising.", "weaknesses": "The presentation of this work is poor, which makes it very hard to understand the core idea of this work and assess its soundness and contribution. Specific examples include:\n- Several notations are never defined, such as $S^t$, $A^t$, $H^{t+1}$, $h_i^t$, $h_i$, etc.\n- The definitions of global policy learner and decision-time planning are not clear. \n- Proposition 3.2 shows the connection between $\\mathcal{U}^{global}$ and $\\mathcal{U}^{global}_Q$. However, it is unclear how could Algorithm 1 converts a global policy learner to a decision-time planner, as claimed in the paper.\n-  What does it mean by policy iteration local updating function? How to plug it into Algorithm 1? Why it can turn the algorithm to Monte Carlo search? \n- What is the definition of $\\sigma$ and how to integrate the constraint on $\\sigma$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4j1EpO1FD4", "reviewer": "Reviewer_W84D", "summary": "This paper studies decision-time planning for general imperfect-information games, such as poker. Previous methods face limitations when dealing with games where the amount of non-public information is extensive, primarily due to the rapid growth in subgame sizes. To address this issue, this paper introduces a framework for decision-time planning, focusing on the idea of update equivalence rather than subgames. Experimental results demonstrate that these algorithms, when applied to Hanabi, 3x3 Abrupt Dark Hex, and Phantom Tic-Tac-Toe, either match or surpass state-of-the-art methods.", "questions": "In terms of the definition of finite-horizon partially observable stochastic games, the observation function should be $\\mathcal{O}_i: \\mathbb{S} \\rightarrow \\mathbb{O}_i$ instead of $\\mathcal{O}_i: \\mathbb{S} \\times \\mathbb{A} \\rightarrow \\mathbb{O}_i$?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The main contribution of this work is proposing a new framework called \"update equivalence\" for decision-time planning in imperfect information games. The key idea is that instead of viewing DTP algorithms as solving subgames, they can be constructed to be equivalent to updates of global policy learners in the limit.", "weaknesses": "I find the proposed methods to be somewhat straightforward and intuitive, and I would encourage the authors to highlight the novelty and distinctiveness of their approach. \n\nThe theoretical results, such as Theorem 3.3, appear to be relatively basic and directly inferred from standard findings. Additionally, these results do not provide a comprehensive characterization of global convergence.\n\n\nIn terms of the empirical evaluation, I have reservations about the performance of the proposed methods, as they don't appear to offer a substantial improvement over existing algorithms. To strengthen the paper, it would be advantageous for the authors to broaden the scope of their evaluation, encompassing more complex scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A2MTtyiEhD", "reviewer": "Reviewer_Vf98", "summary": "The paper studies an equivalence between global policy learners and decision-time planning algorithms for imperfect information games. It argues that by using this equivalence, a new family of algorithms can be derived for solving imperfect information games that do not reply on public information. This makes the algorithms more efficient and more suitable for games where most information is non-public. The authors further tested the proposed approach in the Hanabi game, and demonstrated the advantage of the approach.", "questions": "- What are the objectives of the algorithms (global policy learners and DTP algorithms)? Do they compute an equilibrium of the game, or do they just compute policies for the next iteration? What is the solution concept applied for the games studied?\n\n- What does $g$ represent in $U^{global}: (\\pi_t, g) \\rightsquigarrow \\pi_{t+1}$ when you introduce the global policy learners? \n\n- $\\pi_i$ is initially defined as the policy of player $i$, but when you introduce the global policy learners, $\\pi_t$ seems to be associated with a time step $t$, so what does $\\pi_t$ refer to here? Is there an iterative updating process where a new policy is used in each time step $t$? \n\n- It is said that squiggly arrows are used to indicate randomness in the output. When you write $U_Q^{global} : \\Delta(\\mathbb{A}_i) \\times \\mathbb{R}^{|\\mathbb{A}_i|} \\rightsquigarrow \\Delta(\\mathbb{A}_i)$, the output is already a distribution over $\\mathbb{A}_i$. Do you mean that there is a further randomization over the output distribution (i.e., a distribution over $\\mathbb{A}_i$ is randomly chosen)?\n\n- What is $\\mathcal{P}_\\pi$ in Algorithm 1? It seems undefined. What is $G$ samples in the algorithm?", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 1, "strengths": "The paper seems to study an important problem relevant to interesting and high-impact applications of imperfect information games.", "weaknesses": "The paper is quite hard to follow. Through the current presentation, I don't find a clear message about the main approach and key idea of the work; See Questions. The notation and statements seem to lack clarity and rigor. The results presented look either confusing or trivial (e.g., Theorem 3.3).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)