Approximate State Abstraction for Markov Games

Atsushi Iwasaki; Hiroki Ishibashi; Kenshi Abe

REVIEW 3 major objections 4 minor 36 references

Approximate State Abstraction for Markov Games

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read State aggregation in zero-sum Markov games preserves near-optimal play, up to an error linear in how much Q-values are allowed to differ within a merged block.

desk verdict A solid, incremental extension of approximate state abstraction to zero-sum Markov games; the main proof holds up, and the stress-test concern about Lemma 3 is mistaken. read the letter →

arxiv 2412.15877 v1 pith:RFGCJNBD submitted 2024-12-20 cs.GT cs.AIcs.MA

Hiroki Ishibashi , Kenshi Abe , Atsushi Iwasaki This is my paper · ORCID

classification cs.GTcs.AIcs.MA MSC 91A1591A10

keywords stateabstractionMarkovgameszero-sumdualitygapNashequilibriumminimaxQ-learningaggregationapproximate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether shrinking the state space of a two-player zero-sum Markov game still leaves the players near an equilibrium of the original game. It answers yes: if states are merged only when their optimal state-action values differ by at most ε, the equilibrium computed in the compressed game, when lifted back to the original game, has duality gap at most 12ε/(1−γ)^3. The duality gap here is the largest amount either player could gain by deviating, so the bound quantifies how much abstraction costs in solution quality. The paper derives the same kind of guarantee for three additional aggregation criteria and shows in a Markov Soccer experiment that the abstraction reduces 760 states to under 300 for moderate ε while keeping the gap close to the ground game.

What carries the argument

The load-bearing object is the Q*-similarity abstraction φ_{Q*} together with the weighted abstract game it induces. States in a block are averaged with weight function w to define abstract rewards and transitions, and the abstract game is solved for its Nash equilibrium, which is then lifted back by π*_GA(s)=π*_A(φ_{Q*}(s)). The proof machinery is the duality-gap decomposition into one-sided deviation gains, followed by three perturbation lemmas: Lemma 2 bounds the abstract-versus-ground Q-value gap, Lemma 3 bounds the ground-equilibrium-versus-lifted-policy gap, and Lemma 1 converts a uniform Q-value closeness of δ into a 2δ/(1−γ) value-difference bound. Minimax Q-learning is the algorithm used in the experiments both to estimate Q* for building the abstraction and to solve the abstract game.

What would settle it

Search exhaustively over small two-player zero-sum Markov games: for each game compute Q* exactly, build the coarsest partition satisfying Assumption 1 for a fixed ε, solve the abstract game exactly, and check whether the lifted equilibrium's duality gap exceeds 12ε/(1−γ)^3; one exceeding example would refute Theorem 1, and none would support it.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1. For a two-player zero-sum Markov game with discount factor γ, let φ_{Q*} be an aggregation function that maps ground states with close optimal minimax state-action values into one abstract state; explicitly, if φ_{Q*}(s1)=φ_{Q*}(s2), then |Q*(s1,a)−Q*(s2,a)| ≤ ε for every action profile a. Let π*_GA be the policy profile obtained by playing a Nash equilibrium of the abstract game in the ground game. Then GAP(π*_GA) ≤ 12ε/(1−γ)^3. The proof splits the duality gap into the two one-sided best-response advantages, bounds the difference between abstract and ground Q-values by ε/(1−γ), bounds the performance gap between the ground equilibrium and the lifted abstract equilibrium by 2ε/(1−γ)^2, and then bootstraps through the discount factor. The same template yields bounds for model similarity, Boltzmann distribution similarity, and multinomial distribution similarity in Theorems 2–4.

Load-bearing premise

The bound holds only when states are grouped according to Q*, the optimal state-action values of the original game, because Assumption 1 quantifies the partition in terms of those values; if Q* is not known accurately, the constructed abstraction may violate Assumption 1 and the theorem no longer applies.

Editorial extensions

If this is right

Exact abstraction (ε=0) recovers the ground equilibrium: the lifted equilibrium has duality gap 0, so it is a true Nash equilibrium of the original game.
For a fixed abstraction error ε, the guarantee degrades as 1/(1−γ)^3, so near-deterministic long-horizon games need much finer state partitions to keep the same solution quality.
The model-similarity bound carries an extra factor of |S|, so Q*-based abstraction is the more scalable criterion when Q* values are available.
The Boltzmann and multinomial similarity criteria inherit the Q* bound with inflated ε, so exploration-oriented abstractions also come with explicit performance guarantees.
The Markov Soccer experiment indicates that coarse abstractions with ε around 0.6 keep the duality gap close to the ground game, while coarser partitions produce deadlocks and noticeably larger gaps.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The abstraction starts from Q* of the ground game, so in a truly large game one must first learn those values; a natural extension the paper only mentions in passing is an iterative loop that estimates Q*, abstracts, solves, re-estimates, and refines the partition.
The theorem's bound is uniform over states, so it also certifies each state's deviation loss; the paper reports only aggregate duality gaps, and checking per-state gaps would test how tight the uniform bound is.
The same proof template should extend to other solution concepts or to games with more than two players, but the minimax structure of the duality gap would need a different measure of equilibrium distance.
The experimental duality gaps are approximated with Q-learning rather than computed exactly, so the reported curves support the theory qualitatively but are not a precise test of the constant 12 in the bound.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a legitimate, incremental extension of Abel et al.'s approximate state abstraction from MDPs to two-player zero-sum Markov games. The main theorem's proof holds up; the stress-test note about inequality (12) is mistaken.

What's new: the paper defines Q*-similarity abstraction for TZMGs and proves a duality gap bound of 12ε/(1−γ)^3 for the induced equilibrium. It also gives bounds for model, Boltzmann, and multinomial similarity via reductions to the Q* criterion. That's a real extension of an established program, not a new framework.

The proof of Theorem 1 is mostly clean. Lemma 2 and Lemma 3 follow standard contraction arguments. I checked the specific stress-test concern: inequality (12) claims Q* − Q^{π†} ≤ 0, and it is actually valid. For any fixed opponent policy π2, player 1's best-response value is at least the minimax value V*, so V^{π†} ≥ V* pointwise, and hence Q^{π†} ≥ Q*. The counterexample in the stress-test note actually satisfies (12): it gives Q* − Q^{π†} = −δ/8, which is ≤ 0. So that concern evaporates. There are minor typos—'apggregation' in Assumption 1, 'Extentions' in Section 6, and an arithmetic slip in the proof of Lemma 5 where the bound is looser than needed but still valid.

The real limits are elsewhere. Assumption 1 is defined around Q*, which you don't know until you solve the game. The paper acknowledges this in Section 4.1, but it means the abstraction is an a posteriori guarantee, not a practical cost-saver. The experiments build the abstraction after solving the ground game, and they report approximate duality gaps from Q-learning without error bars or code. The model-similarity bound scales with |S|, and the Boltzmann bound has an e^{1/(1−γ)} factor, so those extensions are mostly formal.

Who should read it: people working on state abstraction for MARL or exploitability in games. It's a solid contribution to that subfield, though not a breakthrough. It deserves a serious referee; the proofs should be checked carefully, but I believe the central result is correct.

Recommendation: send it to review. A referee can fix the typos and ask for cleaner experiments, but the core theory is sound.

Referee Report

3 major / 4 minor

Summary. The paper extends approximate state abstraction from single-agent MDPs to two-player zero-sum Markov games (TZMGs). It defines an abstract game through a state aggregation map and a weighting function, then studies the duality gap of the abstract game's Nash equilibrium when lifted to the ground game. The central theoretical result (Theorem 1) claims that, if states are aggregated by a map satisfying Assumption 1, i.e., states in one block have Q*-values within epsilon for every action profile, then the lifted equilibrium has duality gap at most 12 epsilon / (1 - gamma)^3. Section 6 gives analogous bounds for model similarity, Boltzmann-distribution similarity, and multinomial-distribution similarity, and Section 5 reports Markov Soccer experiments showing the number of abstract states and the duality gap as a function of epsilon.

Significance. If the main bound is established, the paper provides a useful first quantitative extension of Abel et al.'s MDP abstraction bounds to zero-sum Markov games. The explicit polynomial dependence on 1/(1 - gamma), the clean decomposition of the duality gap into two one-sided best-response bounds, and the reduction of three further abstraction criteria to the Q*-based criterion are attractive features. The manuscript is also honest about several limitations, including the need to know Q* to construct the abstraction. However, the proof of the central Lemma 3 currently relies on an invalid inequality, and the proof of Theorem 2 uses a model-similarity condition stronger than the one actually assumed. These gaps are load-bearing and must be repaired before the results can be accepted. The experiments illustrate the trade-off but report only approximate duality gaps and do not provide code or data.

major comments (3)

[§4.2, Lemma 3 and Eq. (12)] The step 'Q*(s,a) - Q^{pi-dagger_1, pi*_GA,2}(s,a) <= 0' is not a consequence of the minimax property (1). Equation (1) characterizes the ground equilibrium pi*, whereas pi*_GA,2 is the lifted equilibrium of the abstract game and is not in general equal to pi*_2. If pi*_GA,2 is suboptimal, player 1's best response can achieve strictly more than V*, making Q^{pi-dagger} exceed Q*. A concrete two-state example (gamma = 0.5, rewards [[0,1],[1,0]] at s1 and [[0,1+delta],[1+delta,0]] at s2, with transitions T:s1->s1, B:s1->s2, T:s2->s1, B:s2->s2) satisfies Assumption 1 with epsilon = delta, yet Q*(s1,(T,L)) - Q^{pi-dagger}(s1,(T,L)) = -delta/8 < 0. Thus the proof of Lemma 3, and therefore of Theorem 1, is invalid as written. The lower-bound half of Lemma 3 appears obtainable by a symmetric min-recursion, so the result may be repairable, but the repair must be supplied.
[§6, proof of Lemma 5 / Assumption 2] Assumption 2 only bounds differences of transition probabilities at the level of abstract blocks, i.e., |sum_{s' in G_A(s'_A)} (P(s'|s1,a) - P(s'|s2,a))| <= epsilon. The proof of Lemma 5 then uses the bound sum_{s'} |P(s'|s1,a) - P(s'|s2,a)| |V(s')| <= gamma epsilon |S| / (1 - gamma). This requires a per-state L1 bound, which Assumption 2 does not provide. A block-sum bound of epsilon does not imply such an L1 bound: two transition distributions can differ by total variation 2 within a single abstract block while all block sums are zero. Therefore the displayed derivation of inequality (13) is not justified, and Theorem 2 as stated is not proved. The assumption should be strengthened to include sum_{s'} |P(s'|s1,a) - P(s'|s2,a)| <= epsilon, or a genuinely different argument is needed.
[§4.1 and §5.2] The abstraction is defined in terms of Q*, the very quantity a solver would be trying to compute. The paper acknowledges this in §4.1 ('minimax Q-learning is used to calculate Q-values for the ground game'), but the practical circularity remains a significant limitation: Theorem 1 is a conditional guarantee for abstractions that are already Q*-consistent, and the experimental protocol in §5.2 first solves the ground game and then aggregates. The manuscript should state explicitly that no computational saving for the original ground game is claimed unless Q*, or a sufficiently accurate approximation of it, is available at no greater cost. This does not invalidate the conditional bound, but it materially affects how the contribution should be read.

minor comments (4)

[§6 heading] The heading 'Extentions' should be 'Extensions'.
[Assumption 1 and Theorem 1 statement] The word 'apggregation' appears in the statement of Assumption 1 and in the sentence before Theorem 1; it should be 'aggregation'.
[§B.2, Eq. (13)] The equality 'epsilon + gamma epsilon |S| / (1 - gamma) = epsilon + gamma(|S|-1) epsilon / (1 - gamma)' is arithmetically incorrect; the correct right-hand side is epsilon (1 + gamma(|S|-1)) / (1 - gamma). The final stated bound of Lemma 5 is consistent with the corrected expression, so this appears to be a typo, but it should be fixed.
[§5.2] The duality gaps reported in Figure 3 are approximations obtained from Q-learning, not exact values, and no code or data are provided. The authors should state approximation errors or use exact dynamic programming on the 760-state game, and should report the number of random seeds used.

Circularity Check

1 steps flagged · score 2.0 of 10

Theorem 1 is a genuine conditional bound; the only circularity is that the Q*-based abstraction (Assumption 1 and the Section 5 pipeline) presupposes the ground-game solution it is meant to avoid, as the authors acknowledge.

self definitional [Section 4.1 (Assumption 1 and following paragraph) and Section 5.2 (Training and Evaluating)]
""To perform an initial abstraction, minimax Q-learning is used to calculate Q-values for the ground game." (Sec. 4.1) "In Markov soccer, we build state abstraction, by first solving the game, then greedily aggregating ground states into abstract states that satisfy the Q∗ criterion." (Sec. 5.2)"

Assumption 1 defines the aggregation by requiring |Q*(s1,a)-Q*(s2,a)| <= epsilon within each abstract block, and the paper's own experimental procedure computes Q* by minimax Q-learning before aggregating. Constructing phi_Q* therefore presupposes the equilibrium values of the ground game, which is exactly the object an approximate-abstraction method is supposed to avoid solving. Theorem 1 is not a restatement of Assumption 1: it propagates the Q*-closeness epsilon through a nontrivial recursion to bound the duality gap. The circularity is methodological and self-acknowledged ('Developing efficient algorithms for discovering abstractions remains open.'), not a collapse of the theorem into its premise, so the score stays low.

full rationale

Score 2 reflects one real but non-fatal circularity. The Q*-based abstraction criterion (Assumption 1) is defined in terms of the ground-game optimal Q-function, and the paper explicitly says the initial abstraction is built by first solving the game (minimax Q-learning, Section 4.1; 'by first solving the game', Section 5.2). For this criterion the abstraction is not a computation-free reduction. Theorem 1 itself is a conditional error bound: given any partition satisfying Assumption 1, it derives GAP(pi*_GA) <= 12 epsilon / (1-gamma)^3 through Lemmas 1-3; that argument does not assume the conclusion and is not a renaming of the input. No load-bearing self-citations or imported uniqueness theorems were found; Shapley (1953) is an external classical result, and the Abel et al. (2016) extension is explicit. The skeptical attack on Lemma 3's inequality (12) is a proof-correctness concern (misapplied minimax property), not a circularity, and does not raise this score.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central theorem's only real input is Assumption 1, plus standard game-theoretic machinery. No constants are fitted to data.

assumptions (5)

ad hoc to paper Assumption 1: the aggregation function ϕQ* satisfies |Q*(s1,a)-Q*(s2,a)| ≤ ε for all action profiles a whenever ϕQ*(s1)=ϕQ*(s2).
Load-bearing condition for Theorem 1; requires knowledge of the ground game's optimal Q-function, which is the main practical caveat.
ad hoc to paper Assumption 2: aggregated states have rewards and transition probabilities within ε per abstract block.
Used in Theorem 2; adapted from Li et al. (2006) and Abel et al. (2016).
standard math Finite state and action spaces, discount factor γ ∈ [0,1), rewards bounded in [0,1].
Standard TZMG definition (Section 2.1); implies all values are bounded by 1/(1−γ).
standard math Shapley's theorem ensures a value and a stationary Nash equilibrium exist for finite discounted TZMGs.
Invoked implicitly in Section 2.2 to define π* and π*_A; the abstract game is also a finite TZMG.
domain assumption The weight function w satisfies Σ_{g∈G(s_A)} w(g)=1 for each abstract state.
Needed to define abstract reward and transition functions; the theorems hold for any such w.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Approximate State Abstraction for Markov Games." pith.science (2026). https://pith.science/paper/RFGCJNBD

@misc{pith2026241215877,
  author       = {Pith},
  title        = {Pith review of: Approximate State Abstraction for Markov Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RFGCJNBD}},
  note         = {Machine review of arXiv:2412.15877}
}

read the original abstract

This paper introduces state abstraction for two-player zero-sum Markov games (TZMGs), where the payoffs for the two players are determined by the state representing the environment and their respective actions, with state transitions following Markov decision processes. For example, in games like soccer, the value of actions changes according to the state of play, and thus such games should be described as Markov games. In TZMGs, as the number of states increases, computing equilibria becomes more difficult. Therefore, we consider state abstraction, which reduces the number of states by treating multiple different states as a single state. There is a substantial body of research on finding optimal policies for Markov decision processes using state abstraction. However, in the multi-player setting, the game with state abstraction may yield different equilibrium solutions from those of the ground game. To evaluate the equilibrium solutions of the game with state abstraction, we derived bounds on the duality gap, which represents the distance from the equilibrium solutions of the ground game. Finally, we demonstrate our state abstraction with Markov Soccer, compute equilibrium policies, and examine the results.

Figures

Figures reproduced from arXiv: 2412.15877 by the authors.

**Figure 2.** Number of states in the abstract Markov soccer [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Duality gap at each iteration in minimax Q [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 29 canonical work pages

[1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...
[2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
[3]

Abe, K.; and Kaneko, Y. 2021. Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games. In AAMAS, 78--87

2021
[4]

E.; and Littman, M

Abel, D.; Hershkowitz, D. E.; and Littman, M. L. 2016. Near optimal behavior via approximate state abstraction. In ICML, 2915--2923

work page 2016
[5]

Brown, N.; and Sandholm, T. 2018. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374): 418--424

2018
[6]

Burch, N.; Johanson, M.; and Bowling, M. 2014. Solving imperfect information games using decomposition. In AAAI, 602--608

work page 2014
[7]

Castro, P. S. 2020. Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes. In AAAI, 10069--10076

work page 2020
[8]

K.; and Srivastava, S

Dadvar, M.; Nayyar, R. K.; and Srivastava, S. 2023. Conditional abstraction trees for sample-efficient reinforcement learning. In UAI, 485--495

work page 2023

Show all 36 references

[9]

Dietterich, T. 1998. The MAXQ Method for Hierarchical Reinforcement Learning. In ICML, 118--126

1998
[10]

Dietterich, T. 1999. State abstraction in MAXQ hierarchical reinforcement learning. In NeurIPS, 994--1000

1999
[11]

Ferns, N.; Panangaden, P.; and Precup, D. 2004. Metrics for finite Markov decision processes. In UAI, 162--169

2004
[12]

Ganzfried, S.; and Sandholm, T. 2013. Action translation in extensive-form games with large action spaces: axioms, paradoxes, and the pseudo-harmonic mapping. In IJCAI, 120--128

2013
[13]

Gilpin, A. 2006. A Competitive Texas Hold'em Poker Player via Automated Abstraction and Real-Time Equilibrium Computation. In AAAI, 1007--1013

2006
[14]

Gilpin, A.; and Sandholm, T. 2006. Finding equilibria in large sequential games of imperfect information. In EC, 160--169

2006
[15]

Gilpin, A.; and Sandholm, T. 2007. Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker. In AAMAS, 1--8

2007
[16]

Gilpin, A.; Sandholm, T.; and S rensen, T. B. 2007. Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas Hold'em poker. In AAAI, 50--57

2007
[17]

Givan, R.; Dean, T.; and Greig, M. 2003. Equivalence notions and model minimization in Markov decision processes. Artificial intelligence, 147(1–2): 163--223

2003
[18]

Guibas, J.; Mardani, M.; Li, Z.; Tao, A.; Anandkumar, A.; and Catanzaro, B. 2022. Efficient Token Mixing for Transformers via Adaptive Fourier Neural Operators. In ICLR

2022
[19]

Johanson, M.; Burch, N.; Valenzano, R.; and Bowling, M. 2013. Evaluating state-space abstractions in extensive-form games. In AAMAS, 271--278

2013
[20]

K.; and Stone, P

Jong, N. K.; and Stone, P. 2005. State abstraction discovery from irrelevant state variables. In IJCAI, 752--–757

2005
[21]

Jonsson, A.; and Barto, A. G. 2000. Automated state abstraction for options using the U-Tree algorithm. In NeurIPS, 1010--1016

2000
[22]

Kroer, C.; and Sandholm, T. 2018. A unified framework for extensive-form game abstraction with bounds. In NeurIPS, 613--624

2018
[23]

J.; and Littman, M

Li, L.; Walsh, T. J.; and Littman, M. L. 2006. Towards a Unified Theory of State Abstraction for MDPs. In ISAIM

2006
[24]

Littman, M. L. 1994. Markov games as a framework for multi-agent reinforcement learning. In ICML, 157--163

1994
[25]

D.; Hennes, D.; Tarassov, E.; Strub, F.; de Boer, V.; Muller, P.; Connor, J

Perolat, J.; Vylder, B. D.; Hennes, D.; Tarassov, E.; Strub, F.; de Boer, V.; Muller, P.; Connor, J. T.; Burch, N.; Anthony, T.; McAleer, S.; Elie, R.; Cen, S. H.; Wang, Z.; Gruslys, A.; Malysheva, A.; Khan, M.; Ozair, S.; Timbers, F.; Pohlen, T.; Eccles, T.; Rowland, M.; Lanc...

2022
[26]

Ravindran, B.; and Barto, A. G. 2003. SMDP homomorphisms: an algebraic approach to abstraction in semi-Markov decision processes. In IJCAI, 1011--1016

2003
[27]

Ravindran, B.; and Barto, A. G. 2004. Approximate homomorphisms: A framework for non-exact minimization in Markov decision processes. In International Conference on Knowledge Based Computer Systems, 19--22

2004
[28]

Shalev-Shwartz, S.; Shammah, S.; and Shashua, A. 2016. Safe, multi-agent, reinforcement learning for autonomous driving. arXiv preprint arXiv:1610.03295

2016 arXiv
[29]

Shapley, L. S. 1953. Stochastic Games. Proceedings of the National Academy of Sciences, 39(10): 1095--1100

1953
[30]

Silver, D.; Huang, A.; Maddison, C. J.; Guez, A.; Sifre, L.; van den Driessche, G.; Schrittwieser, J.; Antonoglou, I.; Panneershelvam, V.; Lanctot, M.; Dieleman, S.; Grewe, D.; Nham, J.; Kalchbrenner, N.; Sutskever, I.; Lillicrap, T. P.; Leach, M.; Kavukcuoglu, K.; Graepel, T....

2016
[31]

P.; Hui, F.; Sifre, L.; van den Driessche, G.; Graepel, T.; and Hassabis, D

Silver, D.; Schrittwieser, J.; Simonyan, K.; Antonoglou, I.; Huang, A.; Guez, A.; Hubert, T.; Baker, L.; Lai, M.; Bolton, A.; Chen, Y.; Lillicrap, T. P.; Hui, F.; Sifre, L.; van den Driessche, G.; Graepel, T.; and Hassabis, D. 2017. Mastering the game of Go without human knowl...

2017
[32]

S.; and Barto, A

Sutton, R. S.; and Barto, A. G. 1998. Reinforcement Learning: An Introduction. MIT Press

1998
[33]

Szepesvári, C.; and Littman, M. L. 1999. A Unified Analysis of Value-Function-Based Reinforcement-Learning Algorithms. Neural Computation, 11(8): 2017--2060

1999
[34]

A.; and Welling, M

van der Pol, E.; Kipf, T.; Oliehoek, F. A.; and Welling, M. 2020. Plannable Approximations to MDP Homomorphisms: Equivariance under Actions. In AAMAS, 1431--1439

2020
[35]

Wang, X.; and Klabjan, D. 2018. Competitive Multi-agent Inverse Reinforcement Learning with Sub-optimal Demonstrations. In ICML, 5143--5151

2018
[36]

Waugh, K. 2013. A fast and optimal hand isomorphism algorithm. In AAAI Workshop on Computer Poker and Imperfect Information

2013

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

, " * write output.state after.block = add.period write newline

ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

[2] [2]

write newline

" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

[3] [3]

Abe, K.; and Kaneko, Y. 2021. Off-Policy Exploitability-Evaluation in Two-Player Zero-Sum Markov Games. In AAMAS, 78--87

2021

[4] [4]

E.; and Littman, M

Abel, D.; Hershkowitz, D. E.; and Littman, M. L. 2016. Near optimal behavior via approximate state abstraction. In ICML, 2915--2923

work page 2016

[5] [5]

Brown, N.; and Sandholm, T. 2018. Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374): 418--424

2018

[6] [6]

Burch, N.; Johanson, M.; and Bowling, M. 2014. Solving imperfect information games using decomposition. In AAAI, 602--608

work page 2014

[7] [7]

Castro, P. S. 2020. Scalable Methods for Computing State Similarity in Deterministic Markov Decision Processes. In AAAI, 10069--10076

work page 2020

[8] [8]

K.; and Srivastava, S

Dadvar, M.; Nayyar, R. K.; and Srivastava, S. 2023. Conditional abstraction trees for sample-efficient reinforcement learning. In UAI, 485--495

work page 2023