Entropy-Regularized Stochastic Games
Yagiz Savas Mohamadreza Ahmadi Takashi Tanaka Ufuk Topcu
math.OC

X-ray emission in the enigmatic  system
    S. Czesla1 P.C. Schneider1 M.
Salz1 T. Klocová2 T. O. B. Schmidt1 J. H. M. M. Schmitt1
    Received ... / Accepted ... 
==========================================================================================

  
In two-player zero-sum stochastic games, where two competing players make decisions under uncertainty, a pair of optimal strategies is traditionally described by Nash equilibrium and computed under the assumption that the players have perfect information about the stochastic transition model of the environment. However, implementing such strategies may make the players vulnerable to unforeseen changes in the environment. In this paper, we introduce entropy-regularized stochastic games where each player aims to maximize the causal entropy of its strategy in addition to its expected payoff. The regularization term balances each player's rationality with its belief about the level of misinformation about the transition model. We consider both entropy-regularized N-stage and entropy-regularized discounted stochastic games, and establish the existence of a value in both games. Moreover, we prove the sufficiency of Markovian and stationary mixed strategies to attain the value, respectively, in N-stage and discounted games. Finally, we present algorithms, which are based on convex optimization problems, to compute the optimal strategies. In a numerical example, we demonstrate the proposed method on a motion planning scenario and illustrate the effect of the regularization term on the expected payoff. 



§ INTRODUCTION

A two-player zero-sum stochastic game (SG) <cit.> models sequential decision-making of two players with opposing objectives in a stochastic environment. An SG is played in stages. At each stage, the game is in a state, and the players choose one of their available actions simultaneously and receive payoffs. The game then transitions to a new random state according to a probability distribution which represents the stochasticity in the environment.

In an SG, each player aims to synthesize a strategy that maximizes the player's expected payoff at the end of the game. Traditionally, a pair of optimal strategies is described by Nash equilibrium <cit.> according to which both players play their best-response strategies against the opponent's strategy. The value of the game then corresponds to the expected payoff that each player receives at the end of the game, if they both play their respective equilibrium strategies.

The concept of Nash equilibrium is based on the assumptions that the players have perfect information about the environment and act rationally <cit.>. However, in certain scenarios, the information that a player has about the environment may not match the reality. For example, in a planning scenario, if the player obtains its information about the environment through surveillance missions performed in the past, it may face with a significantly different environment during the execution of the play. In such scenarios, playing an equilibrium strategy may dramatically decrease the player's actual expected payoff as the strategy is computed under the assumption of perfect information. 

The principle of maximum entropy prescribes a probability distribution that is maximally noncommittal with regard to missing information <cit.>. The principle of maximum causal entropy extends the maximum entropy principle to settings where there is dynamically revealed side information that causally affects the evolution of a stochastic process <cit.>. A distribution that maximizes the causal entropy of a stochastic process (in the absence of additional constraints) is the one that makes all admissible realizations equally probable regardless of the revealed information <cit.>. Therefore, the causal entropy of a player's strategy provides a convenient way to quantify the dependence of its strategy to its level of information about the environment as well as the other player's strategy.


In this paper, we propose a method to synthesize a pair of strategies that balances each player's rationality with its belief about the level of missing information. Specifically, we regularize each player's objective with the causal entropy of its strategy which is causally dependent on the history of play. Therefore, the proposed method allows the players to adjust their strategies according to different levels of misinformation by tuning a parameter that controls the importance of the regularization term. For example, in two extremes, it allows the player to be perfectly rational or to purely randomize its strategy.

We study both entropy-regularized N-stage and entropy-regularized discounted games, and show the existence of a value in both games. We first prove the sufficiency of Markovian and stationary strategies for both players, respectively, in N-stage and discounted games in order to maximize their entropy-regularized expected payoff. Then, we provide algorithms based on a sequence of convex optimization problems to compute a pair of equilibrium strategies. Finally, we demonstrate the proposed methods on a motion planning scenario, and illustrate that the introduced regularization term yields strategies that perform well in different environments.


Related work. In stochastic games literature, the idea of balancing the expected payoffs with an additional regularization term appeared recently in <cit.> and <cit.>. The work <cit.> proposes to bound the rationality of the players to obtain tunable behavior in video games. They study γ-discounted games and restrict their attention to stationary strategies to balance the expected payoffs with the Kullback-Leibner distance of the player's strategies from reference strategies. In <cit.>, authors study N-stage games and consider only Markovian strategies to balance the expected payoffs with the player's sensing costs which are expressed as directed information from states to actions. Unlike this work, we introduce causal entropy of strategies as the regularization term. Additionally, we allow the player's to follow history-dependent strategies and prove the sufficiency of Markovian strategies to attain the value in N-stage games. 

Regularization terms are also used in matrix and extensive form games generally to learn equilibrium strategies <cit.>, <cit.>, <cit.>, <cit.>. When each player uses the same parameter to regularize its expected payoffs with the entropy of its strategy, an equilibrium strategy profile is called a quantal response equilibrium (QRE) <cit.>, and an equilibrium strategy of a player is referred as quantal best response <cit.> or logit choice strategy <cit.>. From a theoretical perspective, the main difference between our approach and the well-studied QRE concept <cit.> is that we establish the existence of equilibrium strategies even if the players use different regularization parameters. Additionally, we provide an efficient algorithm based on a convex optimization problem to compute the equilibrium strategies.

Robust stochastic games <cit.>, <cit.> concern the synthesis of equilibrium strategies when the uncertainty in transition probabilities and payoff functions can be represented by structured sets. Unlike robust SG models, the proposed method in this paper can still be used when it is not possible to form a structured uncertainty set.

In reinforcement learning literature, the use of regularization terms is extensively studied to obtain robust behaviors <cit.>, improve the convergence rates <cit.>, and compute optimal strategies efficiently <cit.>. As stochastic games model multi-player interactions, our approach leverages the ideas discussed in aforementioned work to environments where an adversary aims to prevent a player to achieve its objective. 



§ BACKGROUND

We first review some concepts from game theory and information theory that will be used in the subsequent sections.

Notation: For a sequence x, we write x^t to denote (x_1,x_2,…, x_t). Upper case symbols such as X denote random variables, and lower case symbols such as x denote a specific realization. The cardinality of a set 𝒳 is denoted by |𝒳|, and the probability simplex defined over the set 𝒳 is denoted by Δ(𝒳). For V_1,V_2∈ℝ^n, we write V_1≼V_2 to denote the coordinate-wise inequalities. We use the index set ℤ_+={1,2,…} and the natural logarithm log (·)=log_e (·).


 §.§ Two-Player Stochastic Games

A two-player stochastic game Γ <cit.> is played in stages. At each stage t, the game is in one of its finitely many states 𝒳, and each player observes the current state x_t. At each state x_t, the players choose one of their finitely many actions, and the game transitions to a successor state x_t+1 according to a probability distribution 𝒫:𝒳×𝒰×𝒲→Δ(𝒳) where 𝒰 and 𝒲 are finite action spaces for player 1 and player 2, respectively. The pair of actions, u_t∈𝒰 and w_t∈𝒲, together with the current state x_t∈𝒳 determine the payoff ℛ(x_t,u_t,w_t)≤ℛ<∞ to be made by player 2 to player 1 at stage t. 


A player's strategy is a specification of a probability distribution over available actions at each stage conditional on the history of the game up to that stage. Formally, let ℋ_t=(𝒳×𝒰×𝒲)^t-1×𝒳 be the set of all possible history of plays up to stage t. Then, the strategy of player 1 and player 2 are denoted by σ=(σ_1,σ_2,…) and τ=(τ_1, τ_2,…), respectively, where σ_t :ℋ_t→Δ(𝒰) and τ_t :ℋ_t→Δ(𝒲) for all t. If a player's strategy depends only on the current state for all stages, e.g., σ_t:𝒳_t→Δ(𝒰) for all t, the strategy is said to be Markovian. A stationary strategy depends only on the current state and is independent of the stage number, e.g., σ=(σ, σ,…), where σ:𝒳→Δ(𝒰). We denote the set of all strategies, all Markovian strategies, and all stationary strategies for player i∈{1,2} by Γ_i, Γ_i^M, and Γ_i^S, respectively.

Let μ_t+1(x^t+1,u^t,w^t) be the joint probability distribution over the history ℋ_t+1 of play which is uniquely determined by the initial state distribution μ_1(h_1) through the recursive formula

    μ_t+1(x^t+1,u^t,w^t)=𝒫(x_t+1 | x_t, u_t, w_t)σ_t(u_t | h_t)
                        ×τ_t(w_t | h_t)μ_t(h_t)

where h_t∈ℋ_t is the history of play up to stage t.

A stochastic game with the initial distribution μ_1(x_1) is called an N-stage game, if the game ends after N stages. The evaluation function for an N-stage game is 
 
    J(X^N, U^N, W^N):=
               ∑_t=1^N𝔼^μ_tℛ(X_t, U_t, W_t)+𝔼^μ_T+1ℛ(X_N+1)

where μ_t(·):=μ_t(·)σ_t(·)τ_t(·). Similarly, if the number of stages in the game is infinite, and the future payoffs are discounted by a factor 0<γ<1, the game is called a γ-discounted game. The evaluation function for a γ-discounted game is 

    ∑_t=1^∞γ^t-1𝔼^μ_tℛ(X_t, U_t, W_t).



The player 1's objective is to maximize the evaluation function, i.e., its expected payoff, whereas the player 2 aims to minimize it. A stochastic game is said to have the value 𝒱^⋆, if for an evaluation function f(σ,τ), we have

    𝒱^⋆=max_σ∈Γ_umin_τ∈Γ_w  f(σ,τ)=min_τ∈Γ_wmax_σ∈Γ_u   f(σ,τ).

A pair of strategies (σ^⋆,τ^⋆) is said to be equilibrium strategies if it attains the value of the game.

It is well-known that both N-stage and γ-discounted games have a value for finite state and action sets <cit.>. Moreover, Markovian and stationary strategies are sufficient for players to attain the value in N-stage and γ-discounted games, respectively <cit.>, <cit.>.



 §.§ Causal Entropy

For a sequential decision-making problem where decisions depend causally on the past information such as the history of play, the causal entropy of a strategy is a measure to quantify the randomness of the strategy. Let X^N, Y^N and Z^N be sequences of random variables with length N. The entropy of the sequence X^N causally conditioned on the sequences Y^N and Z^N is defined as <cit.>
 
    H(X^N || Y^N, Z^N ):= ∑_t=1^NH(X_t | X^t-1, Y^t, Z^ t),

where 

    H(X_t | X^t-1, Y^t, Z^ t):=
       -∑_𝒳^N, 𝒴^N,𝒵^NPr(x^t, y^t, z^t)logPr(x_t | x^t-1, y^t, z^t).


The concept of causal entropy has recently been used to infer correlated-equilibrium strategies in Markov games <cit.> and to recover cost functions in inverse optimal control problems <cit.>. In this study, we employ causal entropy to compute an equilibrium strategy profile that balances the players' expected payoff with the randomness of their strategies in stochastic games. 

 In the absence of additional constraints, a strategy σ∈Γ_1 that maximizes the causal entropy H(U^N || X^N, W^N-1) of the player 1, which is conditioned on the revealed history of play, is the stationary strategy σ=(σ,σ,…) where σ(x)(u)=1/ |𝒰|. Therefore, a player that maximizes the entropy of its strategy acts purely randomly regardless of the history of play. On the other hand, a player that regularizes its expected payoff with the entropy of its strategy can be thought as a player that balances its rationality with its belief about the correctness of the underlying transition model of the environment.





§ PROBLEM STATEMENT

We first consider entropy-regularized N-stage games for which we define the evaluation function as

    Φ_N(σ,τ) :=    J(X^N, U^N, W^N)+1/β_1H(U^N || X^N, W^N-1 )
       -1/β_2H(W^N || X^N, U^N-1 ),

where β_1,β_2>0 are regularization parameters that adjust for players the importance of the randomness in their strategies. 
Note that, when β_1=β_2=∞, both players act perfectly rational, and we recover the evaluation function (<ref>). Additionally, since the play is simultaneous, the information of a player's strategy at a given stage is not revealed to the other player. Hence, at each stage, players are allowed to condition their strategies only to observed history of play.

Problem 1: Provide an algorithm to synthesize, if exists, equilibrium strategies in entropy-regularized N-stage games.
 

We next consider stochastic games that are played in infinite stages, and introduce entropy-regularized γ-discounted games for which we define the evaluation function as

    Φ_∞(σ,τ):=   ∑_t=1^∞γ^t-1[𝔼^μ_tℛ(X_t, U_t, W_t)
       +1/β_1H(U_t | H_t )-1/β_2H(W_t | H_t )],

where H_t=(X^t, U^t-1, W^t-1), i.e., the admissible histories of play at stage t. Note that in the evaluation function (<ref>), we discount players' future entropy gains as well as the expected payoff in order to ensure the finiteness of the evaluation function. 

Problem 2: Provide an algorithm to synthesize, if exists, equilibrium strategies in entropy-regularized γ-discounted games.




§ EXISTENCE OF VALUES AND THE COMPUTATION OF OPTIMAL STRATEGIES


In this section, we analyze entropy regularized N-stage and γ-discounted games, and show that both games have values. Then, we provide algorithms to synthesize equilibrium strategies that attain the corresponding game values.


 §.§ Entropy-Regularized N-Stage Games

Searching optimal strategies that solve a stochastic game with the evaluation function Φ_N(σ,τ) in the space of all strategies can be intractable for large N. We begin with establishing the existence of optimal strategies for both players in the space of Markovian strategies.

Markovian strategies are sufficient for both players to attain, if exists, the value in entropy-regularized N-stage games, i.e.,

    max_σ∈Γ_u^Mmin_τ∈Γ_w^MΦ_N(σ,τ)=max_σ∈Γ_umin_τ∈Γ_wΦ_N(σ,τ),
    min_τ∈Γ_w^Mmax_σ∈Γ_u^MΦ_N(σ,τ)=min_τ∈Γ_wmax_σ∈Γ_uΦ_N(σ,τ).


Proof: See Appendix A. 

Next, we show that entropy-regularized N-stage games have a value. Let ρ_t:𝒳×𝒰×𝒲→ℝ be a function and x_t be a fixed state. Additionally, let  

    𝒱_t^σ_t,τ_t(x_t):=𝔼^σ_t, τ_t[   ρ_t(x_t,u_t,w_t)-1/β_1logσ_t(u_t | x_t )
       +1/β_2logτ_t(w_t | x_t )]

be the evaluation function for a one-shot game in which the game starts from the state x_t and ends after both players play their one-step strategy. 


A stochastic game with the evaluation function (<ref>) has a value, i.e.,

    max_σ_t∈Δ(𝒰)min_τ_t∈Δ(𝒲)𝒱_t^σ_t,τ_t(x_t)=min_τ_t∈Δ(𝒲)max_σ_t∈Δ(𝒰)𝒱_t^σ_t,τ_t(x_t).


Proof: It is clear that 𝒱_t(x_t) is a continuous function that is concave in σ_t and convex in τ_t. Additionally, Δ(𝒰) and Δ(𝒲) are compact convex sets. The result follows from von Neumann's minimax theorem <cit.>.

The following proposition states that one can compute the value of the one shot game (<ref>) and synthesize equilibrium strategies by solving a convex optimization problem.



For a given one-shot game with the evaluation function (<ref>), optimal strategies (σ_t^⋆,τ_t^⋆) satisfy

    σ_t^⋆(u_t|x_t)∈
       max_σ_t∈Δ(U)[-1/β_1∑_u_t∈𝒰σ_t(u_t | x_t)logσ_t(u_t | x_t)
       -1/β_2log∑_w_t∈𝒲exp(-β_2∑_u_t∈𝒰σ_t(u_t | x_t)ρ_t(x_t,u_t,w_t))],
       τ_t^⋆(w_t|x_t)=
       exp(-β_2∑_u_t∈𝒰σ_t^⋆(u_t | x_t)ρ_t(x_t,u_t,w_t))/∑_w_t∈𝒲exp(-β_2∑_u_t∈𝒰σ^⋆_t(u_t | x_t)ρ_t(x_t,u_t,w_t)).

Furthermore, the unique value 𝒱^⋆_t(x_t) of the game is given by

    𝒱_t^⋆(x_t)=-1/β_1∑_u_t∈𝒰σ^⋆_t(u_t | x_t)logσ^⋆_t(u_t | x_t)
       -1/β_2log∑_w_t∈𝒲exp(-β_2∑_u_t∈𝒰σ^⋆_t(u_t | x_t)ρ_t(x_t,u_t,w_t)).


Proof: See Appendix A.

It is worth noting that the objective function of the optimization problem given in (<ref>) is strictly concave, and therefore, optimal strategies σ_t^⋆(u_t|x_t) and τ_t^⋆(w_t|x_t) are unique. Additionaly, an optimal strategy with the form (<ref>) is known in the economics literature as quantal best response <cit.>, and for β_1=β_2<∞, the optimal strategies form the well-studied quantal response equilibrium strategies <cit.>.

We remark that the optimization problem in (<ref>) has a closed-form solution which is a function of the optimal strategy τ_t^⋆(w_t|x_t). However, since the closed-form expressions for equilibrium strategies constitute a system of coupled nonlinear equations, the convex optimization formulation provides a more convenient way to compute equilibrium strategies. 


Utilizing the results of above propositions, we now reformulate an entropy-regularized N-stage game as a series of one-shot games through the use of Bellman recursions. Let 

    ρ_t(x_t,u_t,w_t)=ℛ(x_t,u_t,w_t)
           +∑_x_t+1∈𝒳𝒫(x_t+1| x_t, u_t, w_t)𝒱_t+1^σ_t,τ_t(x_t+1),

for t=1,…, N where 𝒱_N+1^σ_t,τ_t(x_N+1)=ℛ(X_N+1). Then, it can be easily verified that 

    Φ_N(σ,τ)=∑_x_1∈𝒳μ_1(x_1)𝒱_1(x_1)

for a given initial distribution μ_1(x_1). Consequently, we obtain the following result.


Entropy-regularized N-stage games have a value. 

Proof: Due to Proposition <ref>, we can focus on Markovian strategies to find an equilibrium point in N-stage games. We start from the stage k=N and compute the value of the one shot game (<ref>), which exists due to Proposition <ref>. Using (<ref>) with (<ref>) for k=N-1,N-2,…,1, we compute the value of N-k+1 stage games. As a result, the claim follows due to the equivalence given in (<ref>). 

Algorithm <ref> summarizes the computation of the pair (σ^⋆,τ^⋆) of optimal strategies for entropy-regularized N-stage games.


Remark: In certain scenarios, one of the players may prefer to play perfectly rationally against a boundedly rational opponent, e.g., β_2=∞. In that case, it is still possible to compute equilibrium strategies by solving a convex optimization problem at each stage. The value of the one-shot game (<ref>) still exists due to the arguments provided in the proof of Proposition <ref>. However, the form of optimal strategies slightly changes to

    τ_t^⋆(w_t|x_t)=min_τ_t∈Δ(W)1/β_1log∑_u_t∈𝒰exp(
                   β_1∑_w_t∈𝒲τ_t(w_t | x_t)ρ_t(x_t,u_t,w_t)),
       σ_t^⋆(u_t|x_t)=
       exp(β_1∑_w_t∈𝒲τ_t^⋆(u_t | x_t)ρ_t(x_t,u_t,w_t))/∑_u_t∈𝒰exp(β_1∑_w_t∈𝒲τ^⋆_t(w_t | x_t)ρ_t(x_t,u_t,w_t)).

It is important to note that, if β_i=∞ for some i∈{1,2}, equilibrium strategies may be not unique since the function log∑exp(·) is not strictly convex over its domain <cit.>.



 §.§ Entropy-Regularized γ-Discounted Games

In this section, we focus on Markovian strategies, whose optimality for N-stage games is shown in Proposition <ref>. Let 𝒱∈ℝ^|𝒳| be a real-valued function, and for a given x∈𝒳, ℒ(𝒱)(x,·,·) : 𝒰×𝒲→ℝ be a function such that

    ℒ(𝒱)(x,σ,τ):=𝔼^σ, τ[ℛ(x,u,w)-1/β_1logσ(u | x )
       +1/β_2logτ(w | x )+γ∑_x'∈𝒳𝒫(x' | x,u, w)𝒱(x')].


As discussed in Proposition <ref>, a one-shot game with the evaluation function ℒ(𝒱)(x,σ,τ) has a value. Therefore, we can introduce the Shapley operator Ψ:𝒱→Ψ(𝒱) from ℝ^|𝒳| to itself specified, for all x∈𝒳, as 

    Ψ(𝒱)[x]:=max_σ∈Δ(U)min_τ∈Δ(W)ℒ(𝒱)(x,σ,τ).


It is clear that the operator Ψ satisfies two key properties: monotonicity, i.e., 𝒱≼𝒱 implies Ψ(𝒱)≼Ψ(𝒱), and reduction of constants, i.e., for any k≥0, Ψ(𝒱+k1)[x]=Ψ(𝒱)[x]+γ k for all x∈𝒳. Consequently, it is straightforward to show that the operator Ψ is a contraction mapping <cit.>. Specifically, we have

    ‖Ψ(𝒱)-Ψ(𝒱)‖_∞≤γ‖𝒱- 𝒱‖_∞,

where ‖𝒱‖_∞=max_x∈𝒳𝒱(x). We omit the details since similar results can be easily found in the literature <cit.>. Then, by Banach's fixed-point theorem <cit.>, we conclude that the operator Ψ has a unique fixed point which satisfies 𝒱^⋆=Ψ𝒱^⋆.

Next, we need to show that the fixed point 𝒱^⋆ is indeed the value of the entropy-regularized γ-discounted game. Let σ^⋆=(σ^⋆,σ^⋆,…) be a stationary strategy such that σ^⋆ is a one-step strategy for player 1 satisfying the fixed point equation, and τ be an arbitrary Markovian strategy for player 2. Denoting by h_t the history of play of length t, one has, by definition of Ψ and σ^⋆, 

    𝔼^μ_t[ℛ(x_t,u_t,w_t)-1/β_1logσ^⋆(u_t | x_t )+1/β_2logτ(w_t | x_t )
       +γ∑_x'∈𝒳𝒫(x' | x_t,u_t, w_t)𝒱^⋆(x') | h_t]≥𝔼^μ_t[𝒱^⋆(x_t)| h_t].

This expression can further be written as

    𝔼^μ_t,μ_t+1[ℛ(x_t,u_t,w_t)-1/β_1logσ^⋆(u_t | x_t )
       +1/β_2logτ(w_t | x_t )+γ𝒱^⋆(x_t+1)| h_t]≥𝔼^μ_t[𝒱^⋆(x_t)| h_t].

Multiplying by γ^t-1, taking expectations and summing over 1≤t<k, one obtains

    ∑_t=1^k-1γ^t-1𝔼^μ_t[ℛ(x_t,u_t,w_t)-1/β_1logσ^⋆(u_t | x_t )+
       1/β_2logτ(w_t | x_t )| x_1]≥𝒱^⋆(x_1)-γ^k𝔼^μ_k+1[𝒱^⋆(x_k+1)| x_1].

Taking the limit as k→∞ and using Proposition <ref>, we obtain

    Φ_∞(σ^⋆,τ)≥𝒱^⋆(x_1).

Similarly, when player 2 plays the optimal stationary strategy τ^⋆=(τ^⋆,τ^⋆,…) against an arbitrary Markovian strategy σ of player 1, we have 

    Φ_∞(σ,τ^⋆)≤𝒱^⋆(x_1).

Then, the combination of (<ref>) and (<ref>) implies the following result.


Entropy-regularized γ-discounted games have a value which satisfies Ψ(𝒱)=𝒱. Furthermore, stationary strategies are sufficient for both players to attain the game value, i.e.,

    max_σ∈Γmin_τ∈ΓΦ_∞(σ,τ)=max_σ∈Γ^Smin_τ∈Γ^SΦ_∞(σ,τ).


Computation of optimal strategies is just an extension of Algorithm <ref>. Note that for γ-discounted games, we use the same one-shot game introduced in (<ref>).  Therefore, optimal decision rules at each stage has the form (<ref>) and (<ref>). Consequently, to compute the optimal strategies, we initialize Algorithm <ref> with an arbitrary value vector 𝒱∈ℝ^|𝒳| and iterate until convergence, which is guaranteed by the existence of a unique fixed point. 




§ A NUMERICAL EXAMPLE

In this section, we demonstrate the proposed strategy synthesis method on a motion planning scenario that we model as an entropy-regularized γ-discounted game. To solve the convex optimization problems required for the computation of equilibrium strategies, we use ECOS solver <cit.> through the interface of CVXPY <cit.>. All computations are performed by setting γ=0.8. 

 As the environment model, we consider a 5×5 grid world which is given in Figure <ref> (top left). The brown grid denotes the initial position of the player 1 which aims to reach the goal (green) state. The red grid is the initial position of the player 2 whose aim is to catch the player 1 before reaching the goal state. Finally, black grids represent walls. 



Let x=(s_1,s_2) be the current state of the game such that x[1]=s_1 and x[2]=s_2 are the positions of the player 1 and the player 2, respectively. At each state, the action space for both players is given as 𝒰=𝒲={right,left,up,down,stay}. For simplicity, we assume deterministic transitions, i.e., 𝒫(x,u,w)∈{0,1} for all x∈𝒳, u∈𝒰 and w∈𝒲. If a player takes an action for which the successor state is a wall, the player stays in the same state with probability 1.

For a given (x,u,w)∈𝒳×𝒰×𝒲, we encode the payoff function ℛ(x,u,w) as the sum of two functions such that ℛ(x,u,w)=ℛ_1(x,u,w)+ℛ_2(x,u,w) where 

    ℛ_1(x,u,w)=∑_x'[1]=G𝒫(x' | x,u,w), 
       ℛ_2(x,u,w)= -𝒫(x' | x,u,w)    if  x'[1]=x'[2]≠G
     0    otherwise.


Note that the payoff function defines a zero-sum game which is won by the player 1, if it reaches the goal state before getting caught, and by the player 2, if it catches the player 1 before reaching the goal state. 

We first compute Nash equilibrium strategies in the absence of causal entropy terms, i.e., β_1=β_2=∞, by employing standard linear programming formulation <cit.> for zero-sum games. Starting from the initial state, an equilibrium strategy for the player 1 is to move towards the goal state by taking the action right deterministically, and for the player 2 is to chase the player 1 by taking the action up in the first two stages, and then, take the action right until reaching the goal state. Therefore, a perfectly rational player 1 wins the game with probability 1 no matter what strategy is followed by the player 2. 

To illustrate the drawback of playing with perfect rationality, we assume that there is another wall in the environment about which the players have no information while they compute the equilibrium strategies, i.e., the players use the nominal environment (top left) to compute the equilibrium strategies. First, we consider the case that the wall is between the goal state and the player 1, as shown in Figure <ref> (middle left). In this case, if the player 1 follows the Nash equilibrium strategy, the probability that it reaches the goal state becomes zero. Therefore, following the Nash equilibrium strategy makes the player 1 significantly vulnerable to such changes in the environment. 




To investigate the tradeoff between rationality and randomness, we compute 9 different strategies for player 1 by using β_1=β_2=2,3,…,10, and let it play against the perfectly rational player 2 which follows its Nash equilibrium strategy computed on the nominal environment (top left). The winning probabilities of player 1 under different strategies are shown in Figure <ref> (right) for the corresponding environments given in Figure <ref> (left). This specific scenario demonstrates that, by choosing β=6, the player 1 can obtain a robust behavior against unforeseen changes in the environment, i.e., the winning probability is around 20%, without sacrificing too much from its optimal performance, i.e., around 15%, if the structure of the environment remains the same. It is worth noting that the asymptotical performance of the player 1 as β→∞ approaches to its performance under Nash equilibrium strategy as discussed in <cit.>. Additionally, the importance of the randomness for the player 1 increases as β→0, and using smaller β values negatively affects the performance after a critical point, i.e., β=4.

Finally, one can argue that the tradeoff occurs in this specific scenario only if the unpredicted wall is between the player 1 and the goal state. To justify the choice of β value, we also consider the scenario in which the unexpected wall occupies another state which is shown in Figure <ref> (bottom left). In this case, as shown in  Figure <ref> (bottom right), the use of β=6 result in a strategy that guarantees around 80% winning probability. Therefore, the entropy-regularized strategy of the player 1 still provides an advantage against unpredicted changes without sacrificing too much from the optimal performance.




§ CONCLUSIONS AND FUTURE WORK

We consider the problem of two-player zero-sum stochastic games with entropy regularization, wherein the players aim to maximize the causal entropy of their strategies in addition to the conventional expected payoff. We show that equilibrium strategies exist for both entropy-regularized N-stage and entropy-regularized γ-discounted games, and can be computed by solving a convex optimization problem. In numerical examples, we applied the proposed approach to a motion planning scenario and observed that by tuning the regularization parameter, a player can synthesize robust strategies that perform well in different environments against a perfectly rational opponent.

Extending this work to multi-agent reinforcement learning settings, as discussed in <cit.>, is an interesting future direction. Future work can also investigate the effect of entropy regularization term on the convergence rate of learning algorithms as discussed in <cit.>.


IEEEtran


§ APPENDIX A

Proof of Proposition <ref>: We show the sufficiency of Markovian strategies only for the maximin problem. The proof for the minimax formulation follows the same lines with the arguments provided below. 

The proof is based on backward induction on the stage number 1≤k≤N. Let 

    𝒱_k:=max_σ∈Γ_umin_τ∈Γ_w∑_l=k^N𝔼^μ_l[ℛ(X_l, U_l, W_l)
       -logσ_l(U_l | H_l )/β_1+logτ_l(W_l | H_l )/β_2]+𝔼^μ_T+1ℛ(X_N+1)

be the value of the N-k stage problem. Then, we can write the value of N-k stage problem recursively as

    𝒱_k=max_σ_kmin_τ_k𝔼^μ_k[ℛ(X_k, U_k, W_k)-1/β_1logσ_k(U_k | H_k )
                +1/β_2logτ_k(W_k | H_k )+𝔼^𝒫[𝒱_k+1]].

Base step: k=N. Let σ_N and τ_N^⋆ be an arbitrary strategy for player 1 and the optimal strategy for player 2 at stage N, respectively. Let

    λ_N(h_N, u_N, w_N):=μ_N(x^N,u^N-1,w^N-1)
                               ×σ_N(u_N| h_N)τ_N^⋆(w_N| h_N)
 
be the joint distribution induced by σ_N(u_N| h_N) and τ_N^⋆(w_N| h_N). Additionally, let λ_N(x_N,w_N) and λ_N(x_N) be the marginal distributions of λ_N(h_N, u_N, w_N). We construct a new strategy for player 2 as τ_N(w_N| x_N):=λ_N(x_N,w_N)/λ_N(x_N). Let 

    λ_N(h_N, u_N, w_N):=μ_N(x^N, u^N-1,w^N-1)
                               ×σ_N(u_N| h_N)τ_N(w_N| x_N)

be the joint distribution induced by τ_N(w_N| x_N). Then, by construction, we have λ_N(x_N, u_N, w_N)=λ_N(x_N, u_N, w_N), which can be easily verified by calculating the corresponding marginal distributions. (For a similar strategy construction, see Theorem 5.5.1 in <cit.>.)

The inner optimization problem in (<ref>) for k=N reads

    𝒱_N=min_τ_NJ_N^c(λ_N)-J_N^H(λ_N)

where 

    J_N^c(λ_N)=𝔼^λ_N, 𝒫[ℛ(X_N,U_N, W_N)+ℛ(X_N+1)
                           -1/β_1logσ_N(U_N | H_N)]
       J_N^H(λ_N)=1/β_2H_λ_N(W_N| X^N, U^N-1, W^N-1).

Since the strategy σ_N is arbitrarily chosen, it is sufficient to show that J_N^c(λ_N)=J_N^c(λ_N) and J_N^H(λ_N)≤J_N^H(λ_N) in order to establish the sufficiency of Markovian strategies for player 2. The first equality holds by construction. (Note that the log(·) term is indifferent to changes in the strategy of player 2.) The second inequality can be derived as 

    H_λ_N(W_N| X^N, U^N-1, W^N-1)≤ H_λ_N(W_N| X_N)   
    
    = H_λ_N(W_N| X_N)   
    
    = H_λ_N(W_N|  X^N, U^N-1, W^N-1)

where (<ref>) holds since conditioning reduces entropy <cit.>, (<ref>) is because λ_N=λ_N by construction, and (<ref>) is due to the fact that τ_N(w_N | x_N ) is a Markovian strategy. 
 Consequently, for any strategy chosen by player 1 in stage N, player 2 has a best response strategy in the space of Markovian strategies. 

Next, we can assume that player 2 uses a Markovian strategy and show through a similar strategy construction explained above that player 1 has an optimal strategy in the space of Markovian strategies. As a result, the value 𝒱_N depends on the joint distribution μ_N(x^N, u^N-1, w^N-1) only through its marginal μ_N(x_N) and becomes a function of the marginal μ_N(x_N) only.

Inductive step: k=t Assume that Markovian strategies suffice for both players for k=t+1,t+2,…,N. Then, by induction hypothesis, 𝒱_t+1 is a function of μ_t+1(x_t+1) only. Therefore, using the similar construction to the case k=N, we can construct Markovian strategies σ_t(u_t | x_t) and τ_t(w_t | x_t) such that the objective function in the right hand side of (<ref>) attained by σ_t and τ_t is equal to the value of N-t stage problem. As a result, we conclude that Markovian strategies are sufficient for both players to solve the maximin problem (<ref>). 

Proof of Proposition <ref>:
Since the one-shot game has a value, without loss of generality, we focus on the problem max_σ_t∈Δ(𝒰)min_τ_t∈Δ(𝒲)𝒱_t(x_t). For notational convenience, we rewrite the problem as

    max_Q^ijmin_Q^ik∑_jkQ^ijQ^ikρ_ijk-1/β_1∑_jkQ^ikQ^ijlog Q^ij
                             +1/β_2∑_jkQ^ijQ^iklog Q^ik
       subject to ∑_jQ^ij=1,  ∑_kQ^ik=1,   Q^ij≥ 0,   Q^ik≥ 0,
 
where Q^ij=σ_t(u_t|x_t), Q^ik=τ_t(w_t|x_t) and ρ_ijk=ρ_t(x_t,u_t,w_t). Note that due to constraints ∑_jQ^ij=1 and ∑_kQ^ik=1, we can replace 1/β_1∑_jkQ^ikQ^ijlog Q^ij and 1/β_2∑_jkQ^ijQ^iklog Q^ik by 1/β_1∑_jQ^ijlog Q^ij and 1/β_2∑_kQ^iklog Q^ik, respectively. For now, we neglect the non-negativity constraints and write the Lagrangian for the above optimization problem as

    L=   ∑_jkQ^ijQ^ikρ_ijk-1/β_1∑_jQ^ijlog Q^ij
               +1/β_2∑_kQ^iklog Q^ik+λ^j(∑_jQ^ij-1)
               +λ^k(∑_kQ^ik-1)

where λ^j,λ^k are Lagrange multipliers. Then, taking derivative with respect to Q^ik and equating it to zero, we obtain

    ∂ L/∂ Q^ik=∑_jQ^ijρ_ijk+1/β_2log Q^ik_⋆+1/β_2+λ^k=0.

Rearranging terms and using the constraint ∑_kQ^ik=1, we obtain

    Q^ik_⋆=exp(-β_2∑_jQ^ijρ_ijk)/∑_kexp(-β_2∑_jQ^ijρ_ijk)

which is the same as (<ref>). Note that the resulting strategy also satisfies the non-negativity constraint. Plugging Q^ik_⋆ into Lagrangian L, we obtain the optimization problem given in (<ref>) for which the optimal variables correspond to the optimal strategy of player 1. Similarly, the optimal value (<ref>) of the resulting optimization problem is the value of the game. Uniqueness of the value follows from the fact that the value of the game is the optimal value of a convex optimization problem given in (<ref>). 

 