Constant-Memory Strategies in Stochastic Games: A Theoretical and Empirical Study

1 Introduction

Various real-world situations that involve long-term interactions among a group of participants can be modeled as stochastic games, such as negotiation between multiple stakeholders [Baarslag et al., 2016; Baarslag, 2024], bidding and mechanism design in repeated auctions [Iyer et al., 2014; Balseiro et al., 2015; Shen et al., 2020; Su et al., 2024], multi-agent teamwork [Stern, 2019; Mirsky et al., 2022] and even human-robot collaboration [Puig et al., 2023]. Stochastic games, also known as Markov games, model the interactions of these multi-agent systems as a Markov chain over a set of states, where the transitions are triggered by joint ac-

The formalization of stochastic games was first proposed in Shapley's seminal work [Shapley, 1953]. A perfectly rational agent in a stochastic game is supposed to make use of all past histories to determine the next action, and therefore, the notion of strategies, defined as mappings from all possible histories to actions, is inherently complex. The fact that there are infinitely many strategies prohibits the direct application of Nash's theorem for establishing any existence result of equilibria. However, the stationary transitions of stochastic games inevitably draw attention to a highly specialized subclass of time-independent and memoryless strategies that only consider the current states while discarding all past histories, termed stationary strategies. Indeed, the existence of equilibria formed by stationary strategies in n-player general-sum stochastic games was later proven by Fink [1964] and Takahashi [1964], under mild assumptions. Despite its limited expressiveness, the notion of stationary strategies has enabled the community to practically investigate some complex real-world applications, particularly by resorting to multiagent reinforcement learning (MARL) techniques, as advocated by Littman [1994] and implemented in a line of subsequent work [Lowe et al., 2017; Rashid et al., 2020; Yu et al., 2022].

Notably, one would naturally expect strategies in other less restricted forms that can encode a broader class of behavioral patterns, hoping to achieve better payoff outcomes. For example, in the Iterated Prisoner's Dilemma (IPD), if only stationary strategies are considered, there is a unique Nash equilibrium where both players choose to defect all the time, resulting in the lowest overall payoff. However, even with the ability to remember only one past action played by the opponent, the well-known Tit-For-Tat (TFT) strategy (starting with cooperation) can be devised. One can easily see that if both players adopt the TFT strategy, they will follow a trajectory of both cooperating throughout the game, resulting in a Nash equilibrium with the highest possible payoff. Apart from other forms of representation, such as strategies represented as finite automata [Rubinstein, 1986; Ben-Porath, 1990; Zuo and Tang, 2015] and even Turing machines [Megiddo and Wigderson, 1986; Knoblauch, 1994; Nachbar and Zame, 1996; Chen et al., 2017b], we focus our main effort on investigating the notion of constant-memory strategies, i.e., mappings from history segments of bounded lengths to actions, mainly because it directly relates to the concept of bounded rationality [Simon, 1990] in general, and highly implementable in practice. Note that this notion has been preliminarily investigated by [Chen et al., 2017a] and [Wang and Lin, 2019]. However, they only focus on behavioral strategy best responses under repeated games, without further discussion on either Nash equilibria or mixed strategies under games with multiple states.

In this paper, we comprehensively study the theoretical properties associated with constant-memory strategies in stochastic games. We begin by presenting the following two results:

1. ACharacterization of Best Responses: Given a constantmemory strategy profile adopted by the opponents, there always exists a best response in the form of a pure constant-memory strategy that makes use of the same length of memory.
2. An Existence Result of Equilibria: Given any finite length of memory, there always exists a Nash equilibrium where all agents adopt constant-memory (but not necessarily pure) strategies using that length of memory.

As a side benefit of using memories of constant lengths, any strategy that uses a shorter memory can always be implemented by one that uses a longer memory. Therefore, the above two results directly imply that any NE formed by shorter-length-memory strategies can be transformed into an NE formed by longer-length-memory strategies, suggesting that the longer the memory used by the strategies, the richer the equilibria one can potentially expect.

Additionally, we provide further results about best responses against mixed constant-memory strategies, mathematically defined as those sampled from a set of support strategies with certain probabilities. This is associated with broad applications in the domain of opponent modeling [Carmel and Markovitch, 1998; Albrecht and Ramamoorthy, 2015; Albrecht and Stone, 2018; Zhu and Lin, 2025], particularly for type-based methods [Albrecht and Ramamoorthy, 2015; Albrecht and Ramamoorthy, 2019; Albrecht et al., 2016; Zhu and Lin, 2025]. However, we demonstrate that:

1. A Negative Result on Strategy Equivalence: An opponent with a mixed constant-memory strategy may not correspond to an equivalent opponent with a single (behavioral) constant-memory strategy in terms of resulting in the same payoff.
2. A Negative Result on Best Responses: The best response against a mixed constant-memory strategy is not necessarily constant-memory, and computing such best responses is computationally hard-possibly even not computable.

In spite of these negative results, we do provide a computational model for solving the best response against a mixed strategy, which (1) demonstrates that those computational models proposed in [Zhu and Lin, 2025] do not overcomplicate the problem; and (2) shows that their methods, which are originally designed for playing against opponents using stationary strategies, can be naturally extended to accommodate ones using constant-memory strategies.

2 Preliminaries

The whole system where the agents interact is modelled as a stochastic game (SG, also known as Markov games) [Shapley, 1953], which can be seen as an extension of both normalform games (to dynamic situations with stochastic transitions) and Markov decision processes (to strategic situations with multiple agents). A stochastic game is a 5-tuple ⟨N , S, A, T, R⟩ given as follows,

1. N is a finite set of n agents.
2. S is a finite set of (environmental) states.
3. A = A1 × · · · ×An is a set of joint actions, where Ai is the action set of agent i. In particular, we write ai as the action of agent i and the one without any subscript a = (ai, a-i) as the joint action.
4. T : S ×A1 × · · ·An ↦→∆(S) defines stochastic transitions among states.
5. Ri : S × A1 × · · ·An ↦→ R denotes the immediate rewards for agent i.

To define best responses and hence equilibria, we need to first define strategies and objectives.

Assuming complete observability and perfect recall, a perfectly rational agent should utilize the entire history, while in memory-restricted cases, an agent can only devise strategies based on past memories of finite lengths. We denote the space of all possible histories of length K ∈ N as HK ≜ (S×A)K . In particular, when K = 0, we have H0 = ∅ meaning that no history can be utilized. Then, given any non-negative integer K, a K-memory strategy for agent i is a mapping from all possible histories with lengths less then or equal to K and the current states to (possibly randomized) actions, mathematically denoted as πi : H≤K × S ↦→ ∆(Ai) where H≤K ≜ ∪Kk=0Hk . Let ΠKi denote the set of all such K-memory strategies for agent i. For convenience, we let H∞ = (S ×A)∗ denote the set of complete histories that an agent with perfect recall can possibly memorize, and therefore, Π∞i is the set of all possible infinite-memory strategies for agent i of the form πi : (S × A)∗ × S ↦→ ∆(Ai). A direct consequence is that ΠKi ⊆ ΠK′ i ⊆ Π∞i for any nonnegative K ≤ K′ . Among them, one of the most popular class of strategies is Π0i , termed stationary strategies. To be clear, we use the term constant-memory to distinguish from those infinite-memory strategies, and use the term K-memory when this specific K needs to be emphasized.

The objective for each agent is to maximize its accumulated discounted rewards (a.k.a. the discounted-payoff scenario, as opposed to the average-payoff scenario). We let Ri,t denote the reward signaled to agent i at step t, similarly for St and ai,t, then the overall utility under a policy profile (πi, π-i) starting from any arbitrary state S ∈ S is

πi is said to be the best response of π-i, denoted as πi ∈ BR(π-i), if

requiring that a πi must outperform any other in Π∞i to serve as the best response. Note that, to compare the values of two strategy profiles, one must ensure that the limit of the righthand side (RHS) in Equation (1) exists in the first place. Also note that, some pairs of πi and π′i may not be comparable in the above sense, as this comparison requires value dominance across all possible states.

3 Best Responses and Nash Equilibria

We first characterize the best response of an agent when all the other opponents are equipped with constant-memory strategies with the same non-negative (and finite) memory length.

Theorem 1. Given πj ∈ ΠKj with K ∈ Z for all j ̸= i , i.e., all the other agents are adopting constant-memory strategies with the same finite memory length K, there must exist a pure K-memory strategy for agent i as a best response.

Proof sketch. As the full proof involves some fundamental (and probably tedious) derivations, we defer it to Appendix A.1. The main issue is that, in general, the decision process from the perspective of agent i is an infinite Markov Decision Process (MDP), where the state space encompasses infinitely many histories (of all possible lengths), and transitions/rewards are jointly controlled by the stochastic game dynamics as well as the other opponents. However, we can formally show that there exists a finite MDP that is strategically equivalent. Consequently, among all the optimal solutions of this constructed MDP, there must be a stationary and deterministic policy, which corresponds to a K-memory pure strategy of agent i. While it implies that using memory length up to K is sufficient, chances are that there may also exist best responses of a shorter memory K′ < K, as later discussed in Section 5.1.

This proof is summarized in our code implementation. 1

One can immediately see the following corollary where the opponents use constant-memory strategies but with potentially different memory lengths. The justification is straightforward: all the opponents can be jointly viewed as a "superagent", and consequently this "super-agent" is adopting a (maxj̸=i{Kj})-memory strategy. Therefore, the best response for the pivotal agent shall also be of (maxj̸=i{Kj})- memory. One may also note that it pertains to some recent work on asymmetric memory [Fujimoto et al., 2024]; however, we leave it to future work.

Corollary 1. Given πj ∈ ΠKj j with each Kj ∈ Z for all j ̸= i, i.e., all the other agents are adopting constant-memory strategies but with varying memory lengths, there must exist a pure (maxj̸=i{Kj})-memory strategy for agent i as a best response.

As best responses are well established, we now examine whether an equilibrium exists when everyone best responds to each other.

Definition 1 (Nash Equilibrium). A strategy profile {π∗ i }i∈N is a Nash equilibrium (NE) if

Theorem 2. There exists an NE when the agents are all adopting K-memory strategies, for any arbitrary nonnegative finite K.

1 Please refer to kMemBR.ipynb in our code.

Proof sketch. As previously, we also summarize this proof into a ready-to-run code implementation. 2

We postpone the full proof to Appendix A.2. Similarly to Nash's proof of his well-known existence theorem, here we construct a mapping to iteratively refine those agents' strategies, which operates by adjusting the probability of each action at each state based on its non-negative advantage, followed by a normalization step. It can be formally shown that there is a bijection between the fixed points of this refinement mapping and the solutions to the system of equations that characterizes NEs with K-memory strategy profiles under a given stochastic game.

The above existence result implies the following. Consider two agents playing a stochastic game, where agent 1 employs a two-memory strategy and agent 2 uses a threememory strategy. If agent 1 asserts that it will adhere to its two-memory strategy, agent 2 may identify another twomemory strategy as a best response, potentially yielding the same payoff but allowing for memory saving. Conversely, if agent 2 can convince agent 1 that it will maintain its threememory strategy, agent 1 may find it advantageous to switch to a three-memory strategy as a better response.

Note that the above theorem is not a direct consequence of Nash's existence theorem, as we only discuss randomizing actions within a single strategy, rather than randomizing across multiple strategies, which we will refer to as mixed strategies in the next section.

Another benefit of constant-memory strategies is that any K-memory strategy can be represented as a K′ -memory strategy, provided that K′ ≥ K, by simply utilizing the most recent K records. Thus, we arrive at the following corollary.

Corollary 2. Any payoff profile that is reached by an NE under a K-memory strategy profile can also be realized by another NE under a K′ -memory strategy profile, if K′ ≥ K.

4 Best Responses toMixed Strategies: A Tournament Perspective

We have established that the best response to a single (possibly randomized) constant-memory strategy results in another constant-memory strategy. The next natural question is: what is the best response to a set of constant-memory strategies played according to a specified distribution? A further related question is: can a mixed strategy be converted into a singleton constant-memory strategy? If this is feasible, then the best response must also be a constant-memory strategy.

In the following two subsections, we will show:

1. In repeated games, if an agent encounters an opponent using a mixed zero-memory strategy, it will yield the same expected utility for this agent to play against an opponent with a single induced zero-memory strategy.
2. In general, when the game involves multiple states or the opponent employs a nonzero-memory strategy, then the best response will be hard to compute (possibly not computable) and time-dependent, which may not be encoded as a finite-memory strategy. Therefore, it implies that the

2 Please refer to kMemNE full.ipynb in our code.

opponent's mixed strategy cannot be equivalently transformed into a singleton constant-memory strategy.

4.1 Mixed Strategies vs Behavioral Strategies

We first emphasize the notion of match. When we say an agent i adopts a K-memory strategy, it means that agent i will select one strategy πi ∈ ΠKi just before a match begins. Once the agent has "confirmed" its strategy, it will not deviate to any other strategies during the match until the termination. Note that some strategies, especially those in Π∞i , may be semantically interpreted as "learning" or "evolving" strategies, as they gradually modify the decisions based on accumulated observations; however, each of them remains a singleton strategy within the strategy space Π∞i . From the perspective of a single agent, we may also use the term episode interchangeably with match, as commonly done in the context of MDPs. The overall utility will be calculated as the expected payoff over all possible matches.

Now we are ready to explain the difference between a behavioral strategy and a mixed strategy. Recall that a Kmemory strategy of agent i is defined as πi : H≤K × S ↦→ ∆(Ai); it is also referred to as a behavioral strategy as it can randomize over actions. By definition, a pure strategy that performs deterministic actions is also considered a behavioral strategy. A mixed strategy (for agent i and of K-memory) first specifies its support set ΠK+ i ⊆ ΠKi , where each behavioral strategy πι i ∈ ΠK+ i will be selected with a positive probability pι, before each match begins. Thus, we use a tuple (ΠK+ i , ⃗ p) to denote a mixed strategy for agent i. Intuitively, when an agent is playing against a mixed strategy (ΠK+ i , ⃗ p), it simply means this particular agent will encounter an opponent using the behavioral strategy πι i ∈ ΠK+ i for a fraction pι of the whole time.

One may be particularly interested in a specific type of strategies, namely the behavioral strategy obtained by statewise randomization over the actions according to the probability distribution provided by the mixed strategy.

Definition 2 (Mixed-Strategy-Induced Behavioral Strategy). Given a mixed strategy (ΠK+ i , ⃗ p), we define ω(ΠK+ i ,⃗ p) as the behavior strategy induced by this mixed strategy. Formally, for each (H, S) ∈ H≤K × S,

ι The underlying intuition is that, instead of randomly selecting one of the support strategies at the beginning and sticking to it, we also allow an agent to switch to another strategy within the same probability distribution at each timestep during play, resulting in a single behavioral strategy that randomizes over each support strategy at every state. One can see that if the original strategy is a mixed one over a set of K-memory support strategies, then its induced behavioral strategy, according to Definition 2, will still be a K-memory strategy, and its best response will also be a K-memory strategy, as stated in Theorem 1.

We will first demonstrate that in a special case where a stochastic game is reduced to a repeated game and the agents use stationary strategies, a mixed strategy has the same effect as its induced behavioral strategy. However, in general, if a game involves transitions across multiple states or the opponents adopt nonzero-memory strategies, such equivalence does not necessarily hold.

Theorem 3 (Utility equivalence for repeated games). If the stochastic game is merely a repeated game, i.e. S is a singleton, then an agent i's overall utility when playing against a mixed strategy (Π0+ -i , ⃗ p) will be the same as the utility against the induced behavioral strategy ω(Π0+ -i ,⃗ p) .

We omit the elaboration here; one may refer to the detailed proof in Appendix A.3. The intuition behind is quite clear: if it is stateless and memoryless, then mixing over strategies is the same as mixing over action.

Theorem 4 (Utility Equivalence Does Not Hold for General Stochastic Games). In general, when a stochastic game involves multiple states, an agent i's overall utility when playing against a mixed stationary strategy (Π0+ -i , ⃗ p) is not necessarily the same as the utility against the induced behavioral strategy ω(Π0+ -i ,⃗ p) .

Proof sketch. We here provide some intuitions, while the full proof is deferred to Appendix A.4. The key issue is as follows. Even when an agent plays against a mixed stationary strategy, its overall utility is the expectation of the returns of playing against each of the support strategies (each corresponding to a multi-step MDP), involving |Π0+ -i | contraction mappings. However, when it plays against the induced behavioral strategy, its utility is computed by evaluating only one MDP induced by ω(Π0+ -i ,⃗ p) , involving a contraction mapping that differs from any of the aforementioned |Π0+ -i |. A counter-example is also provided in Appendix A.5.

As increasing either the length of memory or the number of environmental states results in a multi-state MDP from an individual agent's perspective, a natural implication is that utility equivalence between a mixed strategy and its induced behavioral strategy does not necessarily hold for K-memory strategies once K is positive, even in repeated games.

4.2 Computing BR toMixed Strategies is Hard

We will first show that computing the best response against a mixed K-memory strategy can be reduced to optimally solving an infinite-horizon partially observable MDPs (POMDPs) [Sondik, 1978; Kaelbling et al., 1998]. It turns out the reduced ones belong to a subclass of generic POMDPs, namely Contextual MDP (CMDPs), although it may not necessarily imply less challenging computation. To show that this reduction does not complicate the original problem, we also construct a reduction from the problem of optimally solving CMDPs back to that of computing best responses against mixed strategies in stochastic games.

Theorem 5. Given a mixed strategy profile (ΠK+ -i , ⃗ p) of the opponents, computing the best response for agent i can be reduced to optimally solving an infinite-horizon POMDP.

Proof sketch. Here we only provide some intuition, while the full reduction to POMDPs and the proof of correctness are postponed to Appendix A.6. Basically, a POMDP state consists of the history segment, the environmental state of the stochastic game, and the unobservable opponent strategies. Observations are made by simply discarding the third component of the POMDP state. Transitions across those states that are associated with different opponent strategies are assigned zero probabilities, similarly for rewards. An optimal solution for such a POMDP, in terms of maximizing infinitehorizon discounted rewards, is typically obtained as a mapping from all possible histories (or equivalently, from beliefs over states) to potentially randomized actions [Sondik, 1978; Kaelbling et al., 1998], thus, may not correspond to any finite-memory strategy in general.

One can see that the constructed POMDPs in the above theorem belong to a subclass of generic POMDPs, where a state is composed of directly observable variables and other hidden ones, and there are no transitions among the hidden state variables. This subclass is specially termed as Contextual MDPs (CMDPs) [Hallak et al., 2015; Benjamins et al., 2023]. While CMDPs are special cases of POMDPs, the complexity/computability results for CMDPs remain unresolved. So far, the common conjecture is that CMDPs are not significantly easier to solve than POMDPs in general, and it is proven that optimally solving infinite-horizon POMDPs is undecidable [Madani et al., 2003].

This result highly pertains to discussions on type-based methods for single-agent planning in the presence of multiple other agents [Albrecht and Ramamoorthy, 2015; Albrecht and Ramamoorthy, 2019; Albrecht et al., 2016; Zhu and Lin, 2025]. Albrecht and Ramamoorthy [2015] characterized the general problem from a conceptual standpoint, where each opponent's strategy serves as an oracle that can be queried via Monte Carlo simulations; however, certain intermediate cases were not well formalized. As a supplement, Zhu and Lin [2025] offered a fine-grained spectrum of implementable planners for the stationary base case, where each strategy within the support of the opponent's mixed strategy is stationary. Here, Theorem 5 further generalizes this to constantmemory strategies, enabling all the formulations in [Zhu and Lin, 2025] to be extended to the entire family of constantmemory strategies.

We will also present a reduction in the reversed direction.

Theorem 6. Optimally solving a CMDP can be reduced to computing the best response for an agent i against a profile of mixed zero-memory (i.e., stationary) strategies (Π0+ -i , ⃗ p) adopted by its opponents.

Proof sketch. A CMDP is formally defined as a tuple ⟨C, S, A, fT , fR, γ⟩, where

1. C is a finite set of unobservable contexts, one of which will be selected at the beginning of each episode.
2. fT and fR take a context c ∈ C and output a transition function T c : S ×A ↦→ ∆(S) as well as a reward function Rc : S × A ↦→ R, respectively. The tuple ⟨S, A, T c , Rc , γ⟩ then constitutes an MDP.

One can then construct an SG with two players

where agent 1 with action set A is playing against agent 2 (as a "context controller"), as if the latter holds a set of stationary strategies {πc : S ↦→∆(A′ )}c∈C. It can be shown that such a T0 and {πc}c∈C can be factorized out of fT , i.e., the following system of equations holds simultaneously

We omit the analogous factorization of Rc . It turns out that by an algorithm that resembles the Gram-Schmidt Orthogonalization [Cheney and Kincaid, 2009], one can obtain a feasible factorization of minimum size within polynomial time. The full proof is deferred to Appendix A.7.

To clearly position our results, we highlight several key connections between our findings and the existing literature.

1. If the opponent is allowed to switch between support strategies independently at each state (i.e., a scenario of using a mixed-strategy-induced behavioral strategy), then our construction in Theorem 1 for computing the best response corresponds to solving the belief-induced MDP described in [Zhu and Lin, 2025].
2. Wang and Lin [2019] observed that there may not exist a pure one-memory strategy as a best response against a population of one-memory opponents, each potentially adopting a different strategy (e.g., a tournament). Here, Theorem 5 and 6 provide some formal evidence: in general, the best response is not even within constantmemory; instead, it may incorporate infinite memory.
3. Computing best responses to mixed strategies is a building block of the recursive formulation in the I-POMDP framework [Gmytrasiewicz and Doshi, 2005]. Thus, Theorem 5 and 6 can serve as the missing justification for why recursively incorporating POMDPs or CMPDs, rather than vanilla MDPs, is essential for I-POMDPs.

One may also notice a possible correspondence to Epistemic Game Theory [Dekel and Siniscalchi, 2015], as the latter also investigates type and belief structures, albeit through a different formalism; we intend to establish more rigorous connections in future work.

One may further wonder whether a group of agents can form an NE if all of them play mixed strategies, i.e.,

If the support sets {ΠK+ i }i∈N are exogenously specified, one can invoke Nash's existence theorem, as the game becomes finite. Due to the page limit, we defer the elaboration to Appendix B for interested readers; however, the application of such theoretic results remains unclear. Of greater significance is the following open problem: In general, given a mixed constant-memory strategy, does there exist a best response that is also a mixed constant-memory strategy, rather than an infinite-memory behavioral one?

5 Empirical Study

The purpose of these empirical studies is not to benchmark the RL algorithms mentioned in this section; rather, it is to present an intuitive illustration of the effects of memory. The evaluated domains include two matrix games played sequentially, and one domain borrowed from robotics with raw image inputs.

5.1 Sequential Matrix Games

We consider two matrix games that are played in a repeated manner, namely the Iterated Prisoner's Dilemma (IPD), and the Iterated Traveler's Dilemma (ITD).

The Iterated Prisoner's Dilemma

The payoff matrix is shown in the table below. We also remind the readers of the Axelrod library 3 that implements most of the strategies from the well-known Axelrod's IPD tournament. Our approach can compute the best response of any constant-memory strategy in this library, whether deterministic or randomized. In particular, we would like to highlight a family of strategies, called N-Tit(s)-for-M-Tat(s) (originally named by Harper et al. [2017]), which is a parameterized version of the classic Tit-for-Tat. An agent adopting N-Tit(s)-for-M-Tat(s) will retaliate immediately after it has been defected M times, by responding with defection in the next N rounds. Thus, it is a max(N,M)-memory strategy.

Memory length of the responding strategy

Figure 2: Experimental results of the ITD.

We compute the best responses for various settings of (N,M) and the discount factor γ, and illustrate our findings in Figure 1. We utilize MDPtoolbox [Chad`es et al., 2014] to compute the exact solutions of the formulated MDPs, where the resulted policies are all deterministic ones. One can observe clear phase transitions in the best responses. Reading the figure from right to left, it indicates that when the discount factor is sufficiently large, the best response to N-Tit(s)-forM-Tat(s) is to defect (M-1) times followed by one cooperation, and to repeat this pattern periodically, regardless of N. However, when the agent is less patient by placing less value on future reciprocity, it will consider taking one additional round of defection, leading to permanent mutual defection from the (M+1)-th round onwards.

3 https://github.com/Axelrod-Python/Axelrod

This finding is summarized in a formal theorem that can be mathematically justified. We also compute the closed-form solutions for those values of γ that trigger the phase transition. Please refer to Appendix C for details. Please note that while this paper focuses on the discounted-payoff setting, our code also includes the computation of best responses under the average-payoff setting, although a detailed discussion is omitted here.

We note that readers in the IPD community may be particularly interested in Zero Determinant (ZD) strategies [Press and Dyson, 2012]. Originally derived under the scenario of average payoffs, ZD strategies were later generalized to settings with discounted payoffs. These strategies enable a player to unilaterally enforce a linear relationship between its own payoff and that of its opponent, which does not generally imply anything strong about best responses. That said, certain ZD strategies can constitute NEs: for instance, Tit-for-Tat is both a ZD strategy and a best response to itself.

The Iterated Traveler's Dilemma

One may notice that the aforementioned (M-1)-D-beforeOne-C strategy against N-Tit(s)-for-M-Tat(s) can actually be implemented using only (M - 1) memory instead of max(N,M) memory. Specifically, if there has been no cooperation played by itself in the previous (M - 1) rounds, it should cooperate in the current round; otherwise, it should continue defecting. However, we have not addressed the theoretic case of computing the best response against a Kmemory strategy using only K′ -memory with K′ < K. Note that one cannot formulate a K-memory MDP but compute its optimal policy in the form of K′ -memory using dynamic programming, as this would result in inconsistent policy updates. To circumvent this issue, we can run model-free algorithms, e.g., Q-learning which only requires a form of the policy in advance, to see the outcome K′ -memory strategy.

Therefore, we generalize our previous findings to a broader class of games, called the Iterated Traveler's Dilemma (ITD) [Dasler and Tosic, 2010; Toˇsic, 2016], which repeats over the matrix game of traveler's dilemma [Basu, 1994] with payoffs given as,

where each action ai is an integer variable, also known as a bid. Please note that when i ∈ {1, 2} and ai ∈ {0, 1} for each i, it reduces to the aforementioned prisoner's dilemma. In our study, we consider i ∈ {1, 2} with a more fine-grained action space ai ∈ {0, 1, · · · 10} to render a harder computational problem. As the investigation of ITD is still relatively nascent, we also provide additional background as well as some justification for its significance in Appendix D.

We implement N-Tit(s)-for-M-Tat(s) in spirit, as there are no longer well-defined notions of defections or cooperations.

In this context, if an agent finds that its opponent's last bid is smaller than its own last bid, this will be interpreted as a defection; otherwise, it is treated as a cooperation. Tabular Q-learning is leveraged to compute the best responses with various memory length against N-Tit(s)-for-M-Tat(s) for different values of M. For a specific value of M, we compute the best response using memory lengths ranging from 0 to (M + 1). We illustrate the total (undiscounted) payoff for 100 rounds in Figure 2. It turns out that, when restricted to M ′ -memory, the best response against N-Tit(s)-for-M-Tat(s) is exactly M ′ -D-before-One-C, given any M ′ < M. For example, playing against N-Tit(s)-for-5-Tat(s), the best response restricted to only 3-memory will be Three-D-before-One-C, resulting in the agent exploiting its opponent for 3/4 of the time, with a total payoff = 10 × 25 + 11 × 75 = 1075.

5.2 The Pursuit Domain

The aforementioned two games present clear social dilemmas, such that the technique used in the proof of Theorem 2 may only find NEs where both players defect from the very beginning, regardless of the memory length utilized (cf. the aforementioned notebook 4 ). Therefore, we also conduct some experiments on a more intricate testbed borrowed from the robotics community, namely the Pursuit domain [Gupta et al., 2017]. In this task, 8 pursuer agents attempt to catch 20 random walkers (also called evaders). Each pursuer agent can only observe a limited local range, and once 4 pursuers simultaneously overlap with the same evader, this evader will be removed from the game. An episode terminates immediately after all the evaders are removed. Ideally, these 8 agents will devide into two teams for evader hunting. It is actually a Partially Observable SG (POSG) rather than strictly an SG. We aim to investigate: 1) whether longer memories will lead to improved NEs; 2) how well one agent can respond to the 7 others; 3) how well one team (four agents) can respond to the other team (the rest four).

The main results are presented in Figure 3 focusing solely on the results obtained with DQN [Mnih et al., 2013], as it significantly outperforms other algorithms in this task. Additional benchmarking results using other algorithms, e.g., A2C [Mnih et al., 2016] and PPO [Schulman et al., 2017], along with the detailed hyper-parameters, are provided in Appendix E for the reader's reference. To increase the memory length, we simply stack the historical observations and actions. For multi-agent learning in search for NEs, we equip each agent with an identical network and train them to learn independently. As shown in Figure 3(a), utilizing longer memory indeed helps the pursuers catch the evaders faster, indicating a better NE. We extract the eventual strategy trained with 8-memory as it appears to be the best. In the experiments depicted in Figure 3(b), 7 agents are equipped with this pretrained 8-memory strategy, while the remaining agent learns from scratch to find the best response. In the experiments shown in Figure 3(c), one team of 4 agents are equipped with this pretrained 8-memory strategy, leaving the remaining team of the rest 4 agents learning from scratch to find a best "team" response. As a result, using memories of length 4 and 8 is clearly better than using memories of length one. However, 8-memory responses are not significantly distinguishable from 4-memory responses, which may be attributed to the fact that 4-memory strategies are already sufficient to serve as the best response, or possibly due to some representation error introduced by the deep neural networks.

4 Please refer to kMemNE full.ipynb in our code.

It is also interesting to note that, the improvement, which is reflected by the episode length, made by one agent with the other 7 agents fixed (as shown in Figure 3(b)) is clearly less then that made by a team of agents with the other team fixed (as shown in Figure 3(c)). As we examined, in the former case, there is typically one of the 7 fixed agents who occasionally collaborates with three of them and at other times with the remaining three, creating the pseudo-effect of two four-agent teams. This observation may potentially explain why adding one more learning agent only leads to incremental improvement.

6 Conclusion

In this work, we formally study constant-memory strategies in stochastic games. Some theoretic results for best responses and equilibria in the form of behavioral constant-memory strategies are developed. Moreover, we highlight that best responding to mixed constant-memory strategies is a significantly harder computational problem-possibly even not computable. These results extend prior work in two main aspects: they generalize 1) the findings of [Chen et al., 2017a; Wang and Lin, 2019] from repeated games to stochastic games; and 2) the planning framework in [Zhu and Lin, 2025] from stationary opponents to K-memory ones. We also conduct experiments on well-known social dilemmas as well as a multi-robot domain to verify those theoretic insights.