Training Equilibria in Reinforcement Learning
Authors: Lauro Langosco
David Krueger
Adam Gleave
Venue: Submitted to ICLR 2023 (2023)
Keywords: theory
reinforcement learning
learning dynamics
partial observability
MDP
POMDP
markov decision processes

Abstract: In partially observable environments, reinforcement learning algorithms such as policy gradient and Q-learning may have multiple equilibria---policies that are stable under further training---and can converge to policies that are strictly suboptimal. 
Prior work blames insufficient exploration, but suboptimal equilibria can arise despite full exploration and other favorable circumstances like a flexible policy parametrization.
We show theoretically that the core problem is that in partially observed environments, an agent's past actions induce a distribution on hidden states.
Equipping the policy with memory helps it model the hidden state and leads to convergence to a higher reward equilibrium, \emph{even when there exists a memoryless optimal policy}.
Experiments show that 
policies with insufficient memory tend to learn to use the environment as auxiliary memory,and parameter noise helps policies escape suboptimal equilibria. 

Under review conference paper ICLR 2023
TRAINING EQUILIBRIA IN REINFORCEMENT LEARN- ING
Anonymous authors Paper under double-blind review
ABSTRACT
In partially observable environments, reinforcement learning algorithms such policy gradient and Q-learning may have multiple equilibria- qqulibria-poolcciss that are stable under further training-and can converge to equilibria that are strictly sub- optimal. Prior work blames insufficient exploration, but suboptimal equilibria can arise despite full exploration and other favorable circumstances like flexible policy parametrization. We show theoretically that the core problem is that partially observed environments, agent's 's past actions induce distribution hidden states. Equipping the policy with memory helps model hidden state and leads to convergence to a higher reward equilibrium, even when there exists memoryless optimal policy. Experiments show that policies with insufficient memory tend learn to use the environment auxiliary memory, and parameter noise helps policies escape suboptimal equilibria.
INTRODUCTION
Markov decision processes (MDPs). Q-learning and policy gradient methods are known always converge to an optimal policy (Watkins and Dayan 1992] Bhandari and Russo 2019) subject to the assumptions detailed in Section In non-Markovian environments such partially observable MDPs (POMDPs), this guarantee fails when using Markovian policies: the algorithms don't always converge to an optimal policy, and there may be multiple (suboptimal) policies surrounded by "basins of attraction'. This is true even in the tabular setting with full exploration, where formal convergence guarantees are strongest.
For example, consider the double-tap environment described Figure | The optimal policy in this environment is to always choose action 02. However, policy that favors 0₁ is stuck in local optimum. Thus this policy will never converge to the optimal policy even with further training, despite exploring the full state-action space.
We call policy that fixed under further training an equilibriun of the training process. For policy gradient methods, equilibria correspond to stationary points of the expected return; for Q-lcarning. equilibria are fixed points of the Bellman equation. Pendrith and McGarity (1998) construct an environment in which Q-learning may converge to a suboptimal policy. We extend their finding and show that in POMDPs, policy gradient methods and Q-learning may have multiple training equilibria and sometimes converge to suboptimal equilibrium despite full exploration and other favorable circumstances (described in Section 3).
a,,
a
S
S₂
az. 2
0
Figure 1: The double-tap environment. Arrows are transitions between states, labeled with a corresponding action and reward. The agent rewarded when chooses the same action twice in row. The states $1, 82 are unobserved. The optimal policy is to always choose action 0g However, a policy that favors a is caught in a local optimum, since picking 02 is only profitable once done with high probability (see Figure 2a).

---

Under review conference paper ICLR 2023
Theoretical results. We show that multiple equilibria can only emerge when the distribution of unobserved states depends on past actions (Proposition B. Our interpretation is that a memoryless policy must play coordination game with its past self, and may get trapped in suboptimal Nash equilibria. For some contexts, we formalize this interpretation and show that Nash equilibria of coordination games correspond to the training equilibria of an associated RL environment (Theo- rem 3.2p. A sufficient amount of memory resolves the coordination game and provably implies a unique optimal training equilibrium (Proposition [.I]. Thus memory can be crucial for convergence of RL algorithms even when a task does not require memory for optimal performance.
Empirical results. (Reported in Section 5). We confirm empirically that our theoretical results hold practice. In addition, we show that a memoryless policy often learn environment as auxiliary memory, thus improving convergence in the same way that policy memory does. However, there exist counterexamples in which even flexible environment that allows for external memory is not sufficient to learn optimal policy. We also confirm hypothesis that in environments with multiple equilibria, parameter noise (Rückstießß et al. 2008 Plappert et al. 2018) can lead to convergence to better equilibria, thus providing a novel explanation of why parameter noise observed to be beneficial.
the external
2 BACKGROUND ON POMDPS
Reinforcement learning (RL) (Sutton and Barto 2018) is the problem of training agent that takes actions in an environment order to maximize a reward function. The most common formalism for reinforcement learning environments is the Markov decision process (MDP). An MDP models an environment which is Markovian in the sense that the environment state 8; and reward rı time f depend only on the previous state 8t-1 and the previous action a- I Crucially, in this formalism a policy has access to the entire state St at each step, and thus no memory is necessary to perform optimally.
Most realistic environments are MDPs, since real-world problems are invariably partially observ- able. For example, a driving agent must anticipate the possibility of other drivers emerging from side-roads even if they are currently out of sight. To model partial observability, it is common to ex- tend the MDP formalism to define a partially observable Markov decision process (POMDP) (Aström 1965). The main idea is to model the environment as unobserved MDP, and allow the policy to access observations sampled from an observation distribution O s) conditional on the current state.
Formally, a POMDP is tuple (S, T, O, Rt No), where S is the set of states, A the set of possible actions, O the set of observations, T the transition kernel, O is the conditional distribution of observations, R the reward function, 7 E [0. 1) the discount factor, and no is the initial state distribution. Let &, denote the state at time I. Then a timestep proceeds as follows: an observation is drawn according the distribution O(o; | s.) and given input the policy, the policy outputs an action a, the agent receives reward R(s,, a.), and the next state is generated according to the transition kernel 7(*++1 1 | 8e, az).
3 TRAINING EQUILIBRIA IN POMDPS
It is well-known that Q-learning and policy gradient methods converge to a globally optimal policy if the environment is (fully observable) MDP (Watkins and Dayan 1992 Bhandari and Russo 2019). However, in partially observable envirouments we have no such general guarantees. particular, this section we will study partially observable environments where RL algorithms do converge, but there exist multiple suboptimal.
equilibria-tt to which they might converge, some of which are
is also possible that training algorithm may not converge at all. Q-learning with discontinuous action-seles celionn-election methods") P may end up oscillating between two suboptimal policies (Gordon 1996). However, is known that for Q-learning with continuous action selection, fixed points always exist
In some formulations, the reward may also depend on the current state For example e-greddy action selection (Sutton and Barto 2018).

---

Under review conference paper ICLR 2023
Trajectory grasient
40-
Expected discounted return
Policy
expected retum ((o)
35-
Globally optimal policy
30
Locally aptimal fixed point
25
30
20
15
25
20
0.0 9.
15
0.0
0.6
0.8
1.0
0.5 Kih 12))=
0.4
0.6
nan 155
P probabiiity of taking action
(a) Expected return of memoryless policy. (h) Expected return a policy with a one- Gradient ascent on expected return J (()) con-
step memory m) (tt11) The return is function of policy parameters 9, and 0g. This function has easily reachable global optimum at 0g m(11 [&2) 0 and 0 1, and suboptimal fixed points.
verges to one of the extremes p = or p = 1.
A low probability of aj is preferable, but an
agent that favors aj can stay stuck in the local maximum (orange).
Figure 2: The expected return of parametrized policies in the double-tap environment from Figure An optimal solution to this task requires no memory, yet the optimal policy is more easily reached by a policy with memory. In both cases we use discount factor y 0.95, though the results are not sensitive to the value of the discount factor.
(Perkins and Pendrith 2002). In summary, it is possible for training algorithms to not converge all, but this is relatively rare circumstance that can be mitigated. In the rest of this work, we will assume we are working in a setting in which convergence is guaranteed, though not necessarily to an optimal policy.
To avoid 'spurious' convergence problems, will introduce the following assumptions the environment and the learning algorithm. In the fully observable setting, theses assumptions are enough to guarantee convergence of Q- Q-learning and policy gradient methods to an optimal policy, As we will see, in partially observed environments this is not the case.
Assumption 3.1 (Full exploration). Every state-action pair seen infinitely often during training.
Assumption 3.2 (Flexible policy parametrization). The policy space is closed under policy improve- mende
Assumption 3.3 (Bounded rewards). There exists some Rmax such that for all state-action pairs as.a) E S x A we have R(s, a) & Rmav-
Assumption 3.4 (Robbins-Monro) For all stale-action pairs (s, a), the learning rate (an)a20 satisfies E Onn(i.sa)) = oo and Ei 2 mitiaaa) < cc. Here, nít, 8, a) is the index corresponding the ith time that the agent visits state and takes action a.
3.1 TRAINING EQUILIBRIA
We can view a training algorithm as stochastic mapping A that maps a policy my onto an improved policy F = A(T)).
Example 3.1 (Idealized policy gradient). Idealized vanilla policy gradient is training algorithm
on the space of parametrized policies 11 = [mo; E b} that maps a policy no, to A(TO.) = -0 where
0 +++1 = 0x + R(x)))
R the expected return, and n > is step-size hyperparameter.
Any training algorithm induces a stochastic process in the volicy-space given by (mi, ....... ). It natural to ask what the fixed points of this process are. A training equilibrium of a training algorithm
Tabblar policies satisfy this requirement, do neural networks if they are flexible enough represent any tahular policy.

---

Under review conference paper ICLR 2023
then a policy x e II that in expectation held fixed by the training algorithm: E[A(a)] x. For example, the training equilibria of idealized vanilla policy gradient are all the policies Ty such that their parametrization satisfies V = 0, that is the class of stationary points of the expected return parameter space.
the following we will study two training algorithms in particular: REINFORCE, also called "vanilla policy gradient' (Williams 1992; Achiam 2018) and Q-lcarning (Watkins and Dayan [992). We consider the setting where all Assumptions 3.1 through 3.4 are satisfied. Under these conditions it follows from standard convergence results (Bhandari and Russo 2019] Watkins and Dayan 1992) that in MDPs the set of training equilibria is exactly the set of optimal policies. This is not the case in POMDPs,
show via counterexample in Section 3.2
The core problem is that the conditional distribution ry" (s o) of the hidden state given an observation can vary depending on past actions, thus 17" depends on the policy. Indeed, when does not depend on past actions, then both policy gradient and Q-learning algorithms are guaranteed to converge to an optimal policy.
Proposition 3.1 (Optimality in POMDPs. informal), Assume that the conditional distribution 1y" (s|o) the POMDP state given an observation is independent of the policy in the sense that there exists distribution y such that for all state-observation pairs (s, o) and all policies n, g(s o) = 1 (s o).
Then if conditions 3.7 3 hold, Q-learning and policy gradient methods converge to an optimal policy.
Having identified dependence on past actions as the source of convergence problems, we now discuss simple example of an environment suboptimal training equilibrium.
rigorous statement and proof of Proposition 3.1 is given Appendix C.I
3.2 THE 'DOUBLE-TAP" ENVIRONMENT
This environment is introduced in Figure The optimal policy is to always choose action a2. However, a policy that favors 0j is stuck in local optimum, since picking 0g is only profitable once done with high enough prohability (see Figure 2a
Indeed, consider applying policy gradient method (Sutton, McAllester, et al. (2000) to the double-tap environment. Policy gradient algorithms
stochastic gradient descent to maximize the discounted
return (0) = E |Er=o Y rrrz.. where rr is the reward received in timestep f Since there are no observations in this environment, we can define a policy π using only a single parameter the probability of taking action d₁:
= p
if = ai
(a)
1 1-p otherwise.
The expected single-step return for this policy i
Ex [r] = Pr(s = 81 and a = a1) + 2 Pr(s = and a = a2)
= p² p)
The full discounted reward is then given by (p)) (2² 2(1 - //1p 77), ploutd in Figure 2a As is visible in this plot, gradient ascent may get stuck in the local maximum at p" = - initialized poorly at some po > 2/3.
In terms of the environment dynamics, this is because actions not only determine the reward in the current timestep but also affect future state: choosing action dj always leads to state 81- The policy does not know which state it is in, and so needs to choose an action that works well on average. If the environment is in state $1 with high probability then it is best to pick action 0j, which reinforces the suboptimal equilibrium.
"In non-episodic problems the objective function policy optimization methods the average rate of reward lim >T= B(r.] rather than the full discounted return (Sutton and Barto 2018 chapter 13.6).
This amounts to the same thing in our case, since the rate of reward is constant after the first timestep.
"This isn't 't quite true for the first reward, where the value is simply or 2(1 p). depending whether we start in state 81 8g. We ignore this for simplicity, since the effect the training dynamics is negligible.

---

Under review conference paper ICLR 2023
straightforward solution is then to augment the policy with memory: the policy can condition on the action it took in the previous timestep, it will take action dg conditional on having done the same in the previous timestep, thus making d2 better option than d1- We discuss this approach in Section 4
3.3 CORRESPONDENCE TO NASH EQUILIBRIA AND SELF-PLAY
Nash equilibrium (Nash 1950) is a solution to a non-cooperative game, in which no player can increase their payoff by switching to different strategy so long as the other player's 's strategies are held fixed 2 A crucial assumption in such games is that decisions player has knowledge
made simultaneously: no the other player's move before they move. If this assumption is broken, then the player that goes first could trigger a departure from the Nash equilibrium by playing a non-equilibrium strategy.
This reminiscent of the POMDP setting, in which policy has no knowledge of its own past (or future) history and thus is stuck in an equilibrium determined by its own past actions. Just like in the game-theoretic setting, when policy is allowed to condition on its past it no longer gets stuck in suboptimal equilibria (Section 4
the following we make this analogy formal in two ways. First we show that for every two-player game, there exists a corresponding RL environment with the same dynamics, and that the training equilibria of the environment correspond to the Nash equilibria of the game. Second, point to results from the literature on self-play reinforcement learning, which shows that RL training converges to a Nash equilibrium.
Two-player games. Any two voo-player game can be turned into a 'single-plate paagee-layyr' RL environment by having the RL agent play against a fixed policy. In particular we can choose a "best-response" opponent policy that able to see the history (in contrast the trained policy, which is memoryless), and always chooses the action that would have performed best against previous actions within an episode. An example of this kind of environment is the Battle of the Sexes environment introduced Section 5 A trained policy will converge to a Nash equilibrium, and there is one-to-one correspondence between Nash equilibria and training equilibria.
Theorem 3.2 (Informal). Let E be POMDP constructed from a two-player game G by letting the policy play against best-response strategy. Then the following equivalent:
(i) The policy is
fixed point in
(ii) The policy n is part of a Nash equilibrium in G.
A formal statement and proof of Theorem 3.2 is available in Appendix B
Self-play. In general, equilibria can arise when an agent interacts with other agents that are also learning. copies of itself (i.e. agents that share the same policy). Indeed it is well known that multi-agent RL and self- play converge a Nash equilibrium that is not necessarily Pareto-optimal (Conitzer and Sandholm 2003).
We have shown two formal results that highlight the correspondence between theerthhe Nash equilibria and RL training equilibria. In practice, the analogy seems to extend to contexts outside of self-play or those covered in Theerrem3.2 3.2 Wash-cquilibrium-ll like dynamics can arise whenever an agent's 's past actions affect the environment in a way that the agent cannot condition its future actions When this happens, the agent effectively interacts with its past self and typically ends up in a Nash equilibrium a cooperative game, For example, the double-tap environment equivalent to a coordination game ?? in which two copics (agents that share the same policy) each take an action at every timestep: both get reward if they both take action dj and reward 2 if they both take action d2, and reward otherwise. (We invite the reader to check that this indeed leads the same dynamics).
We provide complete definition Appendix

---

Under review conference paper ICLR 2023
Action probabilities sigmoid(μ) for reference
0.002
0.018
0.119
0.5 0.881 0.982 0.998
2.00
Expected return f(u)
stddev
1.75
stddev 1
stddev = 2
1.50
stddev 4
1.25
1.00
0.75
-6
-2 0 2 4
6
μl (mean of parameter noise, logit scale)
Figure 3: The effect of parameter noise the curve of expected return in the 'double-tap' environment. The blue curve (no parameter noise) is identical to the curve Figure Pajtraasfoooee to logit scale. With increasing noise scale the bad local maximum 'smoothed out' and gradient ascent can more casily converge, when initialized very unfavorably.
MITIGATING FACTORS: MEMORY AND PARAMETER NOISE
4.1 MEMORY CAN ELIMINATE SUBOPTIMAL LOCAL OPTIMA
In MDPs, it is standard to work with policies that are memoryless: the action a depends only on the current observation og, not any previous observations or actions. Many partially observable environments however require memory for optimal play. policy with memory samples an action from a conditional distribution x [aa Oz, m.), where my is the memory state at time t. In the limit, the memory might contain the entire history: m, (Oo, ag, 01...., 9.-1). In this case we say that the policy has unbounded memory. In deep RL practice, is common keep track hidden state which encodes relevant past observations, or concatenate several observations into single input to the policy.
recurrent policies that
We find that memory is useful even when optimal policy does not require memory to solve task. This because policies with (unbounded) memory confer the same convergence guarantees to RL algorithms in POMDPs that hold in the MDP setting.
Proposition 4.1 (Policy memory implies convergence an optimal equilibrium (informal)). Assume the conditions 3.7 3.4 hold. If a policy has unbounded memory, then Q-learning and policy gradient methods are guaranteed converge
optimal policy.
Remark 4.1. If only the past & timesteps are relevant to the environment dynamics and the reward, then a policy memory of maximum length l: is enough obtain the same guarantee.
Formal statements and proofs of Proposition 4.1 and Remark 4. are available in Appendix
In the double-tap environment, switching policy with memory (one timestep is enough) removes suboptimal local maxima from graph of the expected return. This shown in Figure (2 where we use two- parameter policy with a one-step memory. Details on the parametrization and the calculation of the expected return available in Appendix A.1.2
Why not use memory? A practical reason not to use memory is that memoryless policies are simpler implement, and less expensive train and perform inference Moreover, the principle of least privilege (Saltzer and Schroeder 1975) recommends that systems should only be given the minimal capabilities needed. So. if a memoryless policy can achieve the task at hand, it should be favored over policy with memory. For example, memoryless policies cannot leak information from a previous interaction with another user. Memoryless policies are also casier to test and validate, as they depend only on the current state, rather than the entire history of states an exponentially larger space.

---

Under review conference paper ICLR 2023
Double-Tap
Battle the Sexes
1.0
1.0
Success frequency
0.8
Success frequency
0.8
0.6
0.6
0.4
Policy-gradient
0.4
Q-learning
0.2
Q-learning
0.2
param noise
0.0
0.0
1 Parameter noise scale
Parameter noise scale
Figure 4: We confirm that parameter noise is beneficial in the Double-Tap (left) and the Battle of the Sexes environment (right). Blue: parameter noise beneficial for tabular policy gradient converge. Green: Q-learning with external memory does well. Red: memoryless policy does badly.
4.2 PARAMETER NOISE CAN ELIMINATE SUBOPTIMAL LOCAL OPTIMA
Since may not always be feasible or desirable to equip policies with sufficient memory for convergence, we investigate Unfortunately, it is not feasible to equip policies with unbounded memory, investigate parameter noise for policy gradient methods, which alleviate the convergence failures outlined Section 3 Since training equilibria correspond to stationary points of the expected return, it is plausible that more exploration in parameter space is helpful. This is in contrast to exploring in the action space, which Q-learning and VPG already do via stochastic policies. In other words, parameter noise explores at the level strategies ('always take action 02 rather than individual actions ( ("take action 02 in timestep t').
Parumeter noise (RückstieB et al. 2008; Plappert et al. 2018 Fortunato al. 2018) samples a parameter setting (M,,
(p, Σ) at the beginning of episode, then hold that parameter fixed for the duration the episode. At the end of an episode, we update the mean μ via gradient descent:
V Ea [J(O] Es V + 5 33)3
(1)
where ~ (N, /) and we use the reparametrization trick (Kingma and Welling 2014) in the first equality. The covariance > held fixed.
As visible in Figure 3 adding parameter noise effectively 'smoothes out' the curve of the expected return, making an optimal policy easily reachable even for memoryless policy. We confirm this empirically in Section
5
EXPERIMENTS
5.1 DOUBLE-TA
Our first experiment is a sanity check: we confirm experimentally that the properties we show analytically for the double-tap environment in Section alaso hold in practice. Our results in Figure confirm that memoryless policies (Q-learning. in red, and policy gradients, in blue fail to converge to the optimal policy. Parameter noise helpful for policy gradients, with success frequency increasing with the standard deviation of the noise. In addition, we study augmenting the environment with external memory: we augment the action, state, and observation space by allowing the agent to flip a bit in addition to other actions. Every timestep, it observes the value of the bit. The policy itself is still memoryless, but it can learn to use this external memory to perform better on both the environments study. Results shown in Figure
0) often

---

Under review conference paper ICLR 2023
8
Size of ext. memory (bits)
1000
M
Mean Episode Return
7
6
5
4
Size of ext. memory (bits)
3
2
1
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Timesteps
1e7
Timesteps
1e7
Figure In the sequential bandit environment, PPO benefits from external memory. Left: external memory brings additional benefit. Right: after a certain point, the complexity cost additional external memory outweighs the marginal benefit.
5.2 BATTLE OF THE SEXES
Battle of the Sexes a game in which two players must soardinate-withone communication- -n which concert to go Bach Stravinsky. The two players have opposed preferences, but both prefer being together to being alone. This results payoff matrix described in Table Note that this game has two Nash equilibria: (Bach, Bach) and (Stravinsky, Stravinsky).
We turn this game into an RL environment by letting the agent choose the actions of Player 1 and have Player 2 be controlled by the environment. Concretely, the policy action space is A [Bach, Stravinsky]. and the reward is equal to Player I's payoff in Table [ The actions of Player 2 are chosen by the environment to achieve maximal return for Player 2 on average given the agent's past actions the episode: at timestep > 0, Player chooses action
Player argmax dg
(ay,
where PPlayer (a', a) the payoff for Player 2 given that Player takes action a' and Player 2 takes action a. Player 2's first action is chosen uniformly at random.
The two Nash equilibria of the original game correspond to training equilibria of Q-learnig or policy gradient. As discussed in Section 3.3 it is possible to generalize this notion to show that for every two-player game, Nash equilibria correspond to stationary points of the expected return.
Player Bach
Stravinsky
Bach
1,2
0, 0
Player
Stravinsky
0,0
2,
Table 1: Payoff matrix for Battle of the Sexes. Entries are tuples where and 72 are payoffs for player and player respectively.
5.3 SEQUENTIAL BANDIT PROBLEM
We now study how well external memory works practice. all our prior environments there exists an optimal policy that memoryless. We now introduce a new environment in which this not the case: the sequential bandit environment. In this environment there are ten actions A [a1.... .10)- and episode is steps long. The environment returns reward I for every new action taken

---

Under review conference paper ICLR 2023
order starting from d1, that is for all & ......,.)...
1 if actions a1...., 2g-1 have already been taken in this episode
R(s, R() =
0 otherwise.
To reliably execute the optimal policy (in timestep I, take action a()) = a,). the agent needs to remember which actions it has already taken.
We study how memoryless policy fares in an augmented version of this environment. As in Section [. we augment the environment with external memory by allowing the agent to individually flip n bits in addition to its other actions. Every timestep, it observes the values of these bits. For values of n 4 or larger, optimal policy ought to be in principle capable of tracking all ten actions and achieving perfect performance.
Results from training a PPO (Schulman et al. 2017) agent with a feedforward policy are shown in Figure The policy reliably learns to make use of the external memory. However, it does not use it optimally: even an agent given 4-bit external memory does not achieve the optimal reward 10. For low values of n. larger external memory is reliably better, while for large values of n a larger external memory may degrade performance. We hypothesize that this is due to the added complexity the size of the state and action space grows exponentially in n.
6 RELATED WORK
Non-convergence in POMDPs. It is well-known that finding optimal policies in POMDPs is usually harder than in MDPs. In particular, Singh et al. (1994) emphasize the necessity of stochastic policies in POMDPs, and Littman (1994) show that in general, finding optimal policy in a POMDP NP-complete. Pendrith and McGarity (1998) discuss the existence of suboptimal training equilibria in Q-learning. Their analysis does not cover policy gradient methods, nor the benefits of parameter noise or external memory. Similarly, Chades et al. (2002) discuss training equilibria that can arise in multi-agent systems, which are necessarily partially observable. In the context of constrained policy classes, Bhandari and Russo (2019) discuss the failure of policy gradient methods to converge MDPs and use an environment similar to our double-tap tap environment as example.
Memory. Peshkin et al. (1999). Littman (1993), and Jaakkola et al. (1994) propose augmenting context POMDPs, though none them discuss
an environment with external memory suboptimal local optima. More recently, Icarte et al. (2020) propose to make learning extemal memory more efficient by providing action that pushes the current observation onto a "memory" stack. They also show by counterexample that policies not always learn to effectively use external memory.
Parameter noise. Most exploration methods in RL explore the state-action space. Parameter noise (RückstieB et al. 2008) allows for additionally exploring the parameter space. Plappert al. (2018) and Fortunato et al. (2018) show that parameter noise can be beneficial in nigh-dimensional madinuous-contro environments. We provide novel potential explanation for these observations: in partially observed environments, parameter noise can help escape suboptimal training equilibria.
7 CONCLUSION
It is well-known that RL convergence guarantees require adequate exploration. In this work, we have studied distinct but common failure mode: multiple training equilibria for Q-learning and policy gradient in POMDPs. We show that this problem is solved by unbounded memory, and may be alleviated by bounded memory (whether internal the policy, external in the environment). We also show the problem may be resolved by parameter noise, providing a novel explanation of the success of parameter noise in improving convergence of RL training.

---

Under review conference paper ICLR 2023
REFERENCES
Achiam, Josh (2018). Vanilla Policy Gradient. URL:: https://spinniii
openal /
en/Latest/a aastt/lloorra wtwiittss//// /vpg. html (cit. on p.
Aström, Karl Johan (1965). "Optimal Control of Markov Processes with Incomplete State Information
I". eng. In: Journal of Mathematical Analysis and Applications 10, pp. 174-205. ISSN: 0022-247X.
DOE: 10 1016 0022- 24 X 65 > 90154 X URL: hitps / lup lub 1u se
search/ws htwp:///w//e/ee fwwee/llll//eeee 532 3668 88688888678..8 pdf (cit, on p. 2
Bhandari, Jalaj and Daniel Russo (2019), "Global Optimality Guarantees For Policy Gradient Meth-
ods". In: CoRR abs/1190..n 786. arXiv: 1966.. 01786,
URL: httt:://aaa:t org aabs/
1906. 01786 (cit. on pp. D E 9 19).
Chades, ladine, Bruno Scherrer, and François Charpillet (2002). "A Heuristic Approach for Solving the Pursuit Problem", In: Proceedings of the 2002 ACM
DicentralizedPPOMMDE Assessment
Symposium on Applied Computing, pp. 57-62 (cit, on p. P).
Conitzer, Vincent and Tuomas Sandholm (2003). "AWESOME: A General Multiagent Learning Algorithm that Converges in Self- and Learns Best Response Against Stationary Opponents", org/ cs 030 7002 (cit, on p. [5)
In: CoRR es. GT/003000002 URL: /htt::::////ta///
Fortunato, Meire et al. (2018). "Noisy Networks For Exploration In: 6th International Conference on
Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30 May 3, 2018, Conference
Track Proceedings. URI.: https: : opwnrevineiveeeeemme net. forum? ? i www.d=-ww....... (cit. on
pp. (p.
Gordon, Geoffrey J. (1996). Chatlering SARSA(A). CMU Learning Lab Internal Report. Available /httt://wwee //www cs cmu. , www. edu/-ggoodoonnn (cit. on p. p.
Icarte, Rodrigo Toro et al. (Oct. 4. 2020). The act of remembering: a study in partially observable
reinforcement learning. DOI: 0 48550 arxiv 2010 01753 arXiv: 2010. 01753 [cs]
URt:hhttp://arae
or.. abs 201 01 753 (visited on 00/18/022) (cit. on p. 2
Jaakkola, Tommi, Satinder Singh, and Michael Jordan (1994). "Reinforcement Learning Algorithm for
Partially Observable Markov Decision Problems". In: Advances in Neural Information Processing
paper / ww/pppprrrrrrppp.. 1c1d4df596d01da daw.::dddddd00500bbbb0b 7a4a - Abstract html (visited on 09/18/2022) (cit.
Systems. Vol. 7. MIT Press. URI:: htttps: //apter papers nips CC/
994 hash/
on p.
Kingma, Diederik and Max Welling (2014). 'Auto-Encoding Variational Bayes". In: 2nd Inter- national Conference on Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16,
2014. Conference Track Proceedings. Ed. by Yoshua Bengio and Yann LeCun. URL: http:
7 7/arxiv. wwriv.errgaabi abs// /1///////222 1312. 6114 (cit. on p. 7.
L Littman, Michael L. (1993). "An Optimization-Basee Categorization of Reinforcement I Learning
Environments". In: Proceedings of the Second International Conference on From Animals
Animuts 2: Simulation of Adaptive Behavior: Simulation of Adaptive Behavior. Honolulu, Hawai,
USA: MIT Press, pp. 262-270. ISBN: 0262663 1490 (cit. on p. p.
(1994). "Memoryless Policies: Theoretical Limitations and Practical Results". In: From animals animats 3. pp. 238-24556 (cit. on P.
Nash Jr, John F (1950). "Equilibrium points in n-person games". In: Proceedings of the national academy of sciences 36.1. pp. 48-49 (cit. p.
Pendrith, Mark D. and Michael McGarity (1998). "An Analysis of Direct Reinforcement Learning Non-Markovian Domains." " In: ICML. Citeseer, pp. 421 (cit. on pp. [
Perkins, Theodore J. and Mark D. Pendrith (2002). "On the Existence of Fixed Points for Q-Learning and Sarsa in Partially Observable Domains". In: ICML, pp. 490-497 (cit. on p.
Peshkin, Leonid, Nicolas Meuleau, and Leslie Pack Kaelbling (June 27, 1999). "Learning Policies with External Memory". In: Proceedings of the Sixteenth International Conference on Machine Learning. ICML '99. San Francisco. CA. USA: Morgan Kaufmann Publishers Inc., pp. 307-314, ISRN: 978-1-55860-6111111 2-8. (Visited on 09/18/ (9/1822022) (cit. on 19). Plappert, Matthias al. (2018). "Parameter Space Noise for Exploration". In: International Confer-
ence on Learning Representations (ICLR) (cit. on pp. 7 9).
RückstieB, Thomas, Martin Felder, and Jürgen Schmidhuber (2008). "State-dependent exploration for
policy gradient methods"". In: Joint European Conference on Machine Learning and Knowledge Discovery Databases. Springer. pp. 234-249
249 (cit. on pp. 2 7 9
Saltzer, Jerome H and Michael D Schroeder (1 (1975). "The protection of information in computer
systems", In: Proceedings of the IEEE 63.9, pp.
(cit. p. 6).
10

---

Under review conference paper ICLR 2023
Schulman, John al. (2017). "Proximal policy optimization algorithms". In: arXiv preprint arXiv:/707.0634/ (cit. on p. 9).
Singh, Satinder P., Tommi Jaakkola, and Michael I. Jordan (1994). "Learning without state-estimation partially observable Markovian decision processes". In: Machine Learning Proceedings 1994.
Elsevier. pp. 284-292 (cit. on p. (.
Sutton, Richard S and Andrew G Barto (2018), Reinforcement learning: An introduction. MIT press
(cit. on pp. 2 [..
Sutton, Richard S. David A McAllester, et al. (2000). "Policy gradient methods for reinforcement learning with function approximation". In: Advances in neural information processing systems, pp. 1057-1063 (cit. on 4. Watkins, Christopher and Peter Dayan (May 1992). "Technical Note: Q-Learning". In: Machine Learning 8, pp. 279-292. DOI: 1007 / /BB 009 699 (cit. pp.
199..
Williams, Ronald J (1992). "Simple statistical gradient-following algorithms for connectionist rein- forcement learning.. In: Machine learning 8.3, pp. 229 256 (cit. on p.

---

Under review conference paper ICLR 2023
A ENVIRONMENT DESCRIPTIONS
A.I DOUBLE-TAP
Q-LEARNING ALSO HAS MULTIPLE FIXED POINTS
This section shows that just like policy gradient methods, Q-learning also may get stuck in the same
suboptimal local optimum.
In contrast to policy optimization, Q-learning methods learn to approximate the action value function Q" and act E g-greddily based on this estimate. In particular we will cover temporal difference Q- learning. This algorithm samples a transition (o, 0, r; o') based on the current policy and then updates the action-value q(0, a) via
q(0 = g(o, a) + <fr + y max g(0'; ,a) g(0, a))
We call q" a fixed point if the update in Equation 2 is equal to zero in expectation. Formally this means that for all observations and actions o, a,
q' a) 5,0'n-Ta"
(r(s,a) + y (
where the expectation is taken with respect to and o' sampled from the distribution induced (in the limit of t + oo) by the policy ag that acts e-greedily with respect to the parameters q". Such fixed point might not be stable: since the update (2) is stochastic, a random change in parameters could induce a switch to different policy. This sort of switch becomes less likely the the difference between the value max, {(, a') of the optimal action and the value of the next-best action grows.
We will now show that for the environment described by Figure (TODO ref figure) there are multiple mappings q(o, a) that satisfy the fixed point Equation 2 Since in this example there is only single, fixed, observation, that we are using e-greedy exploration, so there are only two possible policies (assuming that g(a)) = q(a²) rarely enough that we can safely ignore it):
omit it from our notation and write q(a) for the action-value. We assume
the policy T which chooses a1 with probability 1 e/2 and dg otherwise.
the policy 22 which chooses 02 with probability 1 - e/2 and d₁ otherwise.
It will be useful to write s ~ for the distribution of states that arises when acting according to policy n. We then write r; Es-e, [r(s, a.] for the expected single-step reward for choosing action a if the agent has been acting according to the policy T, in the past. The rewards specificed in Figure are r($1, a,) 1 and r(s2, 02) = 2 (all other rewards are zero), so this amounts to
r1 (1 e/2) 1, and r2 = (1 - e/2) 2.
Proposition A.I. Assume that the exploration parameter satisfiex < 2/3. Then the action-values
r1/(1-7) =a otherwise,
(i(a)
8 (0477/(1-2
and
+ 1r2 =f==1 r2/(1 -7)
(2(a) = both satisfy the fixed-point equation
otherwise,
Farthermore, q induces policy n. while q2 induces n2-
Proof.
We will begin by showing that q (m1) > (a2) (and the converse for g2). First, note that (a2) = + 7 (01)-
Thus (12) < 1i(aa (a1) if and only if
(1- (1-7)((a)
12

---

Under review conference paper ICLR 2023
Now, (1 (1-7)q(01) 1- e/2, so this equivalent the condition
8/2 >
2/3
which is satisfied by assumption. A similar computation shows that (2(02) > (2(a1).
We now show that is indeed a fixed point, meaning that for all actions a.
(a) E [r(s, a) + max qi (a'))-
simple computation is enough: for 0n we have
E [r(s. + max
ma (1 = + r9(a))
= = - -7)
= =r1/(1-1)
=9((a))
Under ni, the probability of being state 82 e/2. Since r(82, a2) = 2, the expected single-step
reward Eswa, [r(s,az]] 0z)] of taking action a2 is exactly E. Thus
E [r(s, 02) + + max 91 (a') = E + 79h (a1) = q1 (az)
desired. By am analogous argument, Q2 is fixed point as well.
Remark A.I. If the exploration parameter is close to 2/3, then the action-values g(a1) and g(02) are also close. In this case the suboptimal fixed-point may be unstable the sense that the noise the updates can 'dislodge' the policy.
A.1.1 EXPECTED RETURN OF A MEMORYLESS POLICY IN THE DOUBLE-TA TAP ENVIRONMENT
the agent follows the memoryless policy, its expected single-step return
E [r] = Pr(s = 81 and a = a1) + Pr(s = 82 and a = d2) p² + 2(1 p-1 2)
The full discounted reward is then given by
(p) E
Σ 7T=
1=0
7 Erd
10 + 2(1 - pp)3)
p² + 2(1 p)
1 1-y
As is visible from the plot in Figure 2a, this function is convex and not concave, gradient ascent may get stuck local maxima. When the initialization Pa is less than the minimum point y = 2/3, then gradient ascent converges to the global maxima = O. But if >> 2/3, then it converges to the local maxima p 1. So if pa is initialized uniformly at random on [0, 1]. gradient ascent converges to suboptimal policy (a1)
one third of the time.
"hii isn't 't quite for the first reward, where the value is simply or 2(1 p). depending whether we in state 81 8g. We ignore this simplicity, since the effect the training dynamics negligible.

---

Under review conference paper ICLR 2023
A.1.2 EXPECTED RETURN A MOLICY WITH MEMORY IN THE DOUBLE- TAP ENVIRONMENT
We will compute the expected return for policy with one-step memory in the double-tap environment from Figure This is the return plotted Figure 2b
First, note that the state g( time t is fully determined by the action (t-11); if (t=1)) 01 then s( = $1, and similary for and $2. Thus policy with memory my = a(-1)) is equivalent to a policy that can observe the state g(t).
We parametrize the agent via the 'state switch' probabilities E I2,, such that
Ta(ai 82) 01 (a 81) 02.
Our goal is to compute the expected return
.(0)
r'
F(ra]
1=
E(ra],
where is the reward received in timestep t. Recall that 1 if the agent takes action a from state $1, Ft 2 the agent takes action 0g from state s2, and r, otherwise. Thus
E[ra] P(s()) = s1)(1 - 02) (P(s s2)(1 01),
(4)
where P(((o) = 8) is the probability of being in state at time t. This distribution depends on the policy.
Proposition A.2. As l - oo, the state distribution converges to
0,
(x) = lim P(s()) = =s:) 01 02
1-000
for (1,2).
We substitute the stable state distribution given in Proposition A.2 into Equation
Elro] 0, (1 02) 28 01)
01
Thus the expected return (after acting in the environment for long enough that the state distribution has stabilized)
J(0)= = 0, 02) + 282(11 01)
(5)
(01 + 02)(1 -7)
This expression is plotted in Figure 26
Proof of Proposition A.2 A simple computation suffices to check that Poo is the unique distribution
that satisfies the fixed-point equation
(s) = Px (s1) (s)) + Psc (82)TT(() 82)-
remains show that this fixed point iteration converges. do this, consider the sequence (pr).e. where p. = P(s = 81). Then the above fixed point iteration can be written as
P++1 (ar
(81)
pe) 82).
The corresponding transformation that maps pe to PL+1 is
F: p + pm (81) (1 () 82)-

---

Under review conference paper ICLR 2023
remains show that F is contraction. Let p. E [0, 11. then
FF Fql= = (p q))(() ) (q - p)r(ai 122]
(p 9) ( [aa) x(a1 #2))
< p 9l | (a)) m(1 52)
- p g).
Thus contraction, and so pt must converge to fixed point pso = 02/(01 + 02).
A.2 BIT GUESSING
This environment has one hidden state h E {0,1}. observation space O {0, and action space {0. 1)². The goal of the agent is to 'guess' the value of the hidden state, given an observation that is either equal to the hidden state (o = h) or bit-flipped (o h).
In each step, the hidden state is sampled uniformly and independently of any past actions. The agent takes action (Alguess: (hip) {0. 1)a. Reward is determined by
if agness h
r(a,
else.
The value of anip determines the observation at the next timestep: if amp 1, then the next observation flipped; otherwise is equal the hidden state.
An RL algorithm training this environment has two equilibria: one where the policy never takes action Olpi and sets its guess equal to the observation, and one where the policy consistently takes
Cdip and always guesses Oguess
(t) 1 ((t)
A.3 BATTLE OF THE SEXES
Any two-player game can be turned into a 'single-player' RL environment by having the RL agent play against a fixed policy. We choose opponent policy that is able the history (in contrast the agent), and always chooses the action that would have done best against previous actions within an episode. More details in Appendix B
EXPECTED RETURN IN BATTLE OF THE SEXES
Let A be the (finite) action space, and for a E A let ra and r. be the rewards for agent and "opponent" respectively, given that both play action
The expected return of memoryless policy in timestep is equal to
(T(T)) Σ m(a)ra Pr(a, = a),
(6)
aEA
where Pr(a, a) is the probability that the opponent will play in timestep The opponent play depends on past actions: the opponent always plays the action
argmax
I(ar a)
that plays best against the agent's past actions within episode. Setting the 'count" variables c(a) Erge II(a = a). we can write this as
a upp argmax c(a) (a).
The opponent (L.e. environment) play aP is random, since it depends the (random) episode history and in particular on c(a).
We will work out the expected return for the special case A {ar, 02). the standard "battle of the sexes' game with two options. In this case, writing = c(a,) and noting that c(az) t c(a,), ) and that is binomial random variable,

---

Under review conference paper ICLR 2023
Pr(a, 00 =a) Pr(c((1) r1 c(o2) r2))
= Pr(cri am - (t c)r2 > 0)
Pr(c 1)
Σ ( (1 km2+1
where 1 = - / + +
B CONNECTIONS BETWEEN NASH EQUILIBRIA AND RL TRAINING EQULIBRIA
Any two-player game can be turned into a "single-player" RL environment by having the agent play against a fixed 'opponent' policy. The opponent policy is able to see the agent's past actions and always chooses the action that would have done best against the agent's previous actions within episode.
this section we formalize this idea and show that Nash equilibria correspond to stationary points the expected return (and thus are equilibria of the policy gradient algorithm). In particular, any game with multiple Nash equilibria (e.g. 'Battle of the Sexes') will also have multiple training equilibria when turned into an RI. environment in this way.
Definition B.1. Iwo-player game a tuple (S, u). where S S2) is tuple of pure strategy sets S. = {I....,,, k.} and u = (u,, u2) is tuple of payoff functions u4 Si S2 +R
Thus the payoff of player i is given by (1 52), where s; E S, are the strategies of players and 2 respectively. We now construct POMDP by putting an RL agent in the role of player and letting the environment control player 2.
Definition B.2. Let a POMDP from the game G by defining E' (S,A, O,T, T, O. 7, n1o in the following way; set A = Si and let the state space S be the set of all possible action histories of maximum length T' that
(S. u) two-player game. Fix the episode length 0. We construct
T
S =
U
A
where
A A X
copics
We choose the observation space O to be empty, thus the distribution of observations O is trivial. The transition function amounts to appending the current action to the history: for any history h (a1,..., az-1) and action ag the transition kernel is deterministic and given by
if = hu (a)
T(K 1,,
otherwise.
To define the reward function R. we need to set the strategy of the opponent, which we choose to be the average best-response over the episode history: for any timestep 1 after the first.
ore argmax &E &
Σ u2(ar, a).
In the first timestep, 9P is sampled uniformly from Sz. For any history h S and action E A the reward equal the payoff player in the current timestep, that R(h, a) u1 u1(a, APP), where "P is the opponent action chosen as in Equation accordinn to the history h.
For convenience, repeat the definition of a Nash equilibrium:

---

Under review conference paper ICLR 2023
Definition B.3 (Nash Equilibrium), Let G = (S, u) be two-player game, A Nash equilibrium pair of strategies ($1,*2) E S1 x S2 such that for all si, 22 in S1 resp. S2,
un ( 82) s un 82)
u2($1, 2/2 I (2)
In the Battle of the Sexes enviromment, every Nash equilibrium in the original two-player game corresponds to an RL training equilibrium the corresoonding POMDP. We now prove that this is true for all two-player games.
Theorem B.1. Let G = (S.u) be a two-player game and E its associated POMDP. Then the following equivalent:
(i) The policy x is graddent equilibrium in E.
(ii) The siralegy set (s".* (.0000) is Nash equilibrium in G.
Proof. For any S2, define the environment E, by taking copy of E and replacing the best- response opponent strategy with the strategy s. Since s chosen independently of past actions, E, is an MDP and standard convergence guarantees hold: policy gradient always learns an optimal policy. Conversely, any optimal strategy also policy-gradien equilibrium point.
(i) = (is): First, consider the environment Eggy. Since v is equilibrium, it must an optimal policy for Egg. Thus for all E St,
ui (5 8 200 Ui (s", s P..)
Second, by definiton of the best-response strategy up there is no strategy that can do better; thus for all s' S2
(s s') S u2(s" (P
We conclude that (s" 2 is Nash equilibrium.
(ii) = (i): Assume (sT, (PP) is Nash equilibrium. This implies क an optimal policy for E.g;; in particular it is also an equilibrium point. Since s is the optimal response strategy, ा is also policy-gradies equilibrium point in E.
C WHEN DO Q-LEARNING AND POLICY GRADIENT METHODS CONVERGE IN POMDPs?
convenience we repeat the usual conditions for convergence (apart from full observability). the following we will always assume they are met.
Full exploration (every state-action pair is visited infinitely often).
The rewards are bounded: there exists some Rmx such that for all state-action pairs (s, a) e S x A we have R(s, < Rmax-
Flexible enough representation.
policy gradient: the policy space closed under policy improvement (Bhandari and Russo 2019).
For Q-learning: the representation of the Q-function is tabular (Watkins and Dayan 1992).
The learning rates satisfy the standard Robbins-Mome conditions: for all state-action pairs (s, a), the learning rate (a.)n20 satisfies Σ An(i..,,)) = xo and Σ o (it...)) < oc. Here, n(i, a) is the index corresponding to the ith time that the agent visits state and takes action

---

Under review conference paper ICLR 2023
C.I THE CONDITIONAL STATE DISTRIBUTION UNAFFECTED BY THE POLICY
Proposition C.1. Let E A,,,, O, R, (,,))))) be a finite POMDP. For any policy n, let 1f" be the distribution on states induced by the policy, and let
Olo | ( 0) Eves O ('))"(*))
be the conditional distribution of state S given observation o O.
Assume that the conditional distribution is independent of the policy in the sense that there exists some such that for all stale-obser state-obeevvttio pairs vis o) 1f" (s o). Further assume that all the conditions listed in the beginning of Appendix [ holdd Then Q-learning and policy gradient are guaranteed to converge an optimal policy.
Proof. The main idea is that we can construct an MDP E' that is equivalent to the POMDP E in the sense that it generates the same trajectories. Then the standard convergence guarantees apply.
Indeed, consider the MDP E' (S', A. T, Hi', m,)),, where S' =O. O. The transition function T" is defined such that for o' E O and a A,
(' a.
Σ Old' 18))('' [s,a)n(s eE8
and the stochastic reward is given by
a) R(s.a)
where s ~ ry(s o). By construction, the dynamics E and E' are equivalent: indeed, all we've done is replace the transition function T with a new kernel that marginalizes over states, and made the reward function stochastic.
Standard results for convergence in MDPs (Bhandari and Russo 2019 Watkins and Dayan 1992) now suffice to show that Q-learning and policy gradient learn an optimal policy in E" and thus in E.
C.2 SUFFICIENT POLICY MEMORY
The core problem in POMDPs is that the distribution 1y (s observation depends the policy æ. We should be able to fix this by conditioning on past observations and actions as well: that is, we equip the policy with memory.
o) the unobserved state given an
this section we will show that if policy has unlimited memory (that is, it can condition on the entire history) then RL algorithms always learn an optimal policy (Proposition C.2 in all POMDPs. In addition, if the observed environment is k-Markov then the memory only needs to be able to store the past timesteps.
Proposition C.2. Let (S, O, R, Y, mo) be POMDP. Consider a parametrized policy no that has memory, that is can condition all past states and observations: the action a, of time is sampled from no(- on, da.
0t-1, oz) If this policy trained using tabular Q-learning or 00-10 .0.....0-11.
VPG it benefits from the standard convergence guarantees (Bhandari and Russo 2019 Warkins and Dayan 1992) in MDPs.
The main idea here is to show that we can construct an MDP whose states consist of the entire POMDP history, and then show that this is equivalent to an agent with sufficient memory. Let E' = (S, A, O,T, O, R. 7, 1/o be a POMDP as in Proposition C.2
We will now construct an MDP E' (S' A'. R') such that training memoryless policy in E' is equivalent to training setup Proposition
Set to be the set of all states of the form s' = (Op, ay...., 01-1, oe, 0x) for I T where T is the maximum number of timesteps within an episode. Let A'' = A. Let T(s', ad) be the distribution over states s" such that s" s' U (a', o), where U is the 'extend' operation and is the observation from E distributed conditional on the history s' U (a'). Finally, set the reward R' (s's', a') o') to be a random variable R'(s', a') = R(s, d'), where the POMDP state is distributed conditional on the history s' (a').

---

Under review conference paper ICLR 2023
Now E" is a well-defined MDP with stochastic rewards. Well-known results (Watkins and Dayan 1992; Bhandari and Russo 2019) now imply the convergence guarantees we wanted.
Proposition C.3. Let E AS,A, O, T, O, RR % 7,7) be a POMDP. Assume that the environment state is k-Markov in the following sense: at timestep i, conditional on the length-k history h
(o at. 1.......,,.011.. 0,,,1 0t), the state St independent of the full history: (st hb) Ri-
Consider a parametrized policy TH that has memory of length k: action at at time sampled from Ta{.I - If this policy is trained using tabular Q-learning or VPG it benefits from the standard
convergence guarantees (Bhandari and Russo 2019: Watkins and Dayan 1992) as in MDPs.
Proof.
Just as previously, we construct an MDP E' policy in E' is equivalent to the training setup in Proposition
(S','','' 17"77 Rt") such that training a memoryless
C.3
S' { [ T) to be the set of all k-histories. Here T is the maximum number of timesteps within an episode.
Let A' = A. For all / S T, let T(4 a) be the distribution over k-histories 1 that results from taking action at step f.
Let h, be h-history and action, and random observation drawn from the distribution
p(o a)
Σ O(o s")T(s" s',a)p((' h).
(Because enviornment k-Markov, the conditional distribution s7(s) It) does not depend on actions or observations more than & timesteps in the past.)
Then we can set the new transition dynamics [h,,, a) to be the distribution over k- h-histories hí such that h is the result of appending and the end of the history h and removing the first timestep recorded in h.
Finally, set the reward R' Rl, a) to be a random variable H²' a) = R(s.a), where the POMDP state is distributed conditional on the history h.
Standard results for convergence in MDPs (Bhandari and Russo 2019 Watkins and Dayan 1992 suffice to show that Q-learning and policy gradient an optimal policy E and thus E.


Reviews:
[{"review_id": "bTP8BCYWKU", "reviewer": "Reviewer_C66v", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper points out that under partial observability algorithms like policy gradient and Q-learning may have multiple training equilibriums, though this observation is, in itself, not entirely novel. On top of this, they present a number of other results and proposals including: \n\n* Showing multiple training equilibria can only arise when the observation conditional state distribution depends on the policy and thus the issue can be understood as a consequence of this dependence. \n\n* Suggesting a correspondence between Nash equilibria and training equilibria.\n\n* Showing that by adding sufficient memory to the state implies convergence to the unique optima.\n\nExperiments are also conducted in simple toy environments which demonstrate how adding memory can improve performance in partially observable domains even if there is an optimal memoryless policy. Further experiments demonstrate how adding parameter noise can allow an agent to converge reliably to better training equilibria when multiple are present, at least in some simple environments.", "summary_of_the_review": "This paper might have the beginning of some interesting directions, but I feel it is far from ready in its current form. Most of the theory is either only vaguely related to the stated point, or already widely known. The empirical results are similarly quite simple and not very robust in their conclusions.", "strength_and_weaknesses": "Strengths\n=========\nThe analogy between Nash equilibria and learning equilibria in POMDPs is somewhat interesting and makes intuitive sense.\n\nThe point that memory is useful in POMDP learning even if the optimal policy does not require memory is interesting and valid.\n\nThe use of parameter noise to escape suboptimal training equilibria is interesting, if not surprising.\n\nWeaknesses\n==========\nThe result that algorithms like Q-learning and policy gradient may have multiple training equilibria is not entirely novel. It is essentially implied by the existence of multiple greedy partitions highlighted in section 6.4 by Bertseka (1996), for example. This prior work is not cited, nor is more recent work on the topic by the same author (Bertsekas 2011). For policy gradient, this result is explicitly given in the cited work of Bhandari and Russo (2019). Though as the authors mention it is in the context of a constrained policy class rather than partial observability, the equivalence between these two cases is well known. Young and Sutton (2020) also highlight the possibility of multiple training equilibria explicitly for Q-learning and policy gradient, which is not cited, but given it seems to only appear on arxiv this omission is forgivable.\n\nProposition 3.1 states that when the observation conditional state probabilities are policy independent, Q learning and policy gradient are guaranteed to converge to an optimal policy in a POMDP. I think what is meant is an optimal memoryless policy, but this is very confusing because no clear distinction is made and elsewhere adding memory is shown to allow convergence to the \"optimal policy\".\n\nThe result that including sufficient memory allows convergence to the optimal policy in a POMDP under appropriate circumstances is well known and hence I don't feel it is a significant contribution. This amounts to saying that with sufficient memory a POMDP becomes an MDP and thus normal guarantees for MDPs apply. This is true generally if one conditions on the full history, and true with a small \"length-k history\" essentially by definition if the environment is k-Markov.\n\nThe result in theorem 3.2, that Nash equilibria of two-player games correspond to training equilibria of a related RL problem is unclear to me and I believe incorrect as stated in the appendix. The MDP is defined by running some arbitrary fixed number of iterations of the two-player game where one opponent (i.e. the environment player) is effectively fixed to play the best response to the actions taken so far by the other (i.e. the \"agent\" player). It seems to be assumed that the environment is then the best response to the policy of the agent player, but this is clearly not true in general. For example, it is obviously untrue if the episode length is 1 as the environment's first action is assumed to be random. It may be true in the limit of infinite episode length, but the present argument is not sufficient to show this. Aside from that, I'm not entirely clear what the point of this theorem is as it doesn't seem to help to explain or motivate anything else in the paper aside from the hand-wavy statement \"In practice, the analogy seems to extend to contexts outside of self-play or those covered in Theorem 3.2\". I think more work needs to be done to motivate this connection.\n\nOverall I found the connection between Nash equilibrium and POMDP learning to be pretty vague in terms of how it is presented in the current paper. In particular, prior to introducing the theorem, it's loosely implied that one can understand POMDPs generally in terms of Nash equilibria. Instead what is supposedly shown is that one can construct a POMDP from a given 2-player game in a particular way and then show a correspondence between Nash equilibria of the game and training equilibria of the POMDP which is quite different and in my mind less interesting.\n\nNothing is said about hyperparameters or how they were chosen for the empirical results, which may be important for interpreting them since I would expect, for example, the performance of PPO with larger numbers of memory bits to depend on these details. Similarly, some details of the environments are missing, including the maximum length of the episodes and how exactly the bit-flipping actions are added to the action space where applicable.\n\nMinor Comments, Corrections and Questions\n=========================================\n* In appendix A it says \"(TODO ref figure)\" which presumably should point to a figure instead.\n\n* In section 3 \"continuous action selection\" is kind of vague and could be clarified.\n\n* In 3.1 A(\\pi_{\\theta_k})=\\pi_{\\theta_{k+1}} should probably operate on the parameters rather than the policy if it is meant to be general enough to include Q-learning. For example in Q-learning one may update the parameters in a way that changes the value, but leaves the (epsilon-)greedy policy the same.\n\n* In the abstract, it says \"Prior work blames insufficient exploration\" but I can't see that this is ever mentioned again and no citation to the specific prior work that does so is given, so this could be taken as an unsubstantiated claim.\n\n* In 3.3 it says that a Nash equilibrium is a solution to a \"non-cooperative game\", but later it says \"Nash equilibrium of a cooperative game\" which is a weird inconsistency.\n\n* Missing reference (??) in 3.3.\n\n* Missing period before \"Unfortunately\" in 4.2.\n\n* It would be good to show a line corresponding to optimal performance in Figure 4.\n\n* In Appendix B T is overloaded to mean both the transition kernel and the episode length.\n\n* What episode length is used in the experiments in Section 5.2?\n\n* In the sequential bandit problem is the bit flip added as an extra action, or is the action the composition of the original actions and optionally flipping each bit?\n\nReferences\n==========\nYoung, Kenny, and Richard S. Sutton. \"Understanding the pathologies of approximate policy evaluation when combined with greedification in reinforcement learning.\" arXiv preprint arXiv:2010.15268 (2020).\n\nBertsekas, Dimitri, and John N. Tsitsiklis. Neuro-dynamic programming. Athena Scientific (1996).\n\nBertsekas, Dimitri P. \"Approximate policy iteration: A survey and some new methods.\" Journal of Control Theory and Applications 9.3 (2011): 310-335.\n\nBhandari, Jalaj, and Daniel Russo. \"Global optimality guarantees for policy gradient methods.\" arXiv preprint arXiv:1906.01786 (2019).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Z_XKB-UtIS", "reviewer": "Reviewer_CVMT", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors draw an analogy between memoryless policies in POMDPs and coordination games. In a POMDP, a memoryless policy can be viewed as playing a game with itself in the past---because it can't remember its past action, it is as if it is playing a one-shot game. The authors show that there is a class of POMDPs where this connection is direct---you can convert between the game and the POMDP and the equilibria are the same in each (the authors define a notion of training equilibria in these memoryless POMDPs).\n\nThe authors claim that this observation provides a new justification for why noise in parameter space is valuable (something that had previously been found empirically)—it can remove local maxima.\n\nIn experiments, the authors explore the effect of parameter noise and the effect of adding additional memory in simple settings. Memory is helpful, but the algorithms do not use it efficient, and too much memory degrades performance.", "summary_of_the_review": "The paper's main contributions tell us something interesting about current practices in RL for POMDPs, but they are somewhat surface-level. The paper is presented in a clear and accessible manner.", "strength_and_weaknesses": "Strengths:\n1. The narrative, mathematics and experiments of the paper are very clear and logical.\n2. Issues relating to training RL in POMDPs are salient to many. The paper gives logical justification for some of these issues.\n\nWeaknesses:\n1. There is not a lot of depth to the observations—the connection between POMDPs and coordination games is fairly surface-level. There is a lot more to POMDPs than those that can be solved optimally with a few states of memory. For example, classic robot control-style with sensor and location uncertainty. I can imagine two ways to improve the paper:\n- Expand the experiments section to more complex environments that still have the interesting properties and measure the impact there\n- Increase the strength of the theoretical connection—a potential avenue for this is to think about connections to evolutionary game theory", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Ml_tJRhuQSD", "reviewer": "Reviewer_QaRE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies several aspects of RL with non-markovian observations under the assumption there is no exploration issue (assumption 3.1) while focusing on asymptotic guarantees. The authors establish several results which are its key contributions:\n1. Under several (quite harsh) assumptions, Q learning and policy gradient converge to an optimal policy (proposition 3.1.).\n2. A correspondence between POMDPs and Nash equilibrium (theorem 3.2.).\n3. Memory based policies improve the asymptotic convergence (proposition 4.1).\nFurther, the authors conduct some simple experiments to exemplify these observations.\n\n", "summary_of_the_review": "Due to the above reasons I believe this work is not yet ready for publications. Specifically:\n1) The theoretical and experimental results are basic.\n2) I currently do not find the different results related to one another.\n3) The main motivation is a toy example. The authors should show (in my opinion) it captures additional interesting problems.\n\nI also attach couple of questions that bothered me while reading thus workL\nPage 2. Nash equilibria in POMDPs\nProposition 3.1:\n1) Shouldn't \\eta have time index? that is, the probability the state at time t is s conditioning on the observation at time t is o?\n2) The assumption here is quite harsh in my opinion and restrict the result to a very specific structure (since \\eta is not a function of pi for all \\pi). Which POMDPs satisfy this assumption? I can see that if the latent state is decodable this assumption is satisfied, but then the environment is not partially observed.\n3) The policy class includes the optimal policy? is it the set of all policies? \n", "strength_and_weaknesses": "Strength.\n\n-) The POMDP setting is of importance. To make RL practically useful it is much needed to improve our understanding and tools. This work established the convergence of two of the most popular RL algorithms for POMDDs under assumptions.\n\nWeaknesses.\n\n-) I find the assumptions made in proposition 3.1. quite harsh. Further, the fact there's no finite time analysis nor explicit treatment of the exploration problem weakens the theoretical results in my opinion.\n\n-) The study of this work is not coherent in my opinion. The theoretical results, in my opinion, are not very much related to one another. It seems there's no concrete message, but rather couple of messages that do not necessarily add together to a coherent story/\n\n-) The experimental results are quite basic. The experiments do not show of new capability, or achieve state of the art performance. Hence, the experimental part does not add much more over the theoretical part.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3O4HUYDnKGs", "reviewer": "Reviewer_A2qp", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In partially observable environments, reinforcement learning algorithms such as policy gradient and Q-learning can converge to equilibria that are strictly suboptimal. The authors point the core problem is that in partially observed environments, an agent’s past actions induce a distribution on hidden states. This problem can be solved by unbounded memory, and may be alleviated by bounded memory.", "summary_of_the_review": "The problem is interesting, and the theoretical analysis is insightful. ", "strength_and_weaknesses": "Strength:\nThe authors show theoretically that multiple equilibria can only emerge when the distribution of unobserved states depends on past actions. A sufficient amount of memory resolves the coordination game and provably implies a unique optimal training equilibrium.\n\nWeaknesses:\nMore empirical results are expected to show the practical application of the theory.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject