Policy Gradient With Serial Markov Chain Reasoning
Authors: Edoardo Cetin
Oya Celiktutan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement learning
Off-policy learning
Markov chain
Continuous control
Machine learning

Abstract: We introduce a new framework that performs decision-making in reinforcement learning (RL) as an iterative reasoning process. We model agent behavior as the steady-state distribution of a parameterized reasoning Markov chain (RMC), optimized with a new tractable estimate of the policy gradient. We perform action selection by simulating the RMC for enough reasoning steps to approach its steady-state distribution. We show our framework has several useful properties that are inherently missing from traditional RL. For instance, it allows agent behavior to approximate any continuous distribution over actions by parameterizing the RMC with a simple Gaussian transition function. Moreover, the number of reasoning steps to reach convergence can scale adaptively with the difficulty of each action selection decision and can be accelerated by re-using past solutions. Our resulting algorithm achieves state-of-the-art performance in popular Mujoco and DeepMind Control benchmarks, both for proprioceptive and pixel-based tasks.


Policy Gradient With Serial Markov Chain Reasoning
Edoardo Cetin Department of Engineering King's College London edoardo... cetin@kcl.......cc.. ac uk
Oya Celiktutan Department Engineering
King's College London oya. cya.celiktutan@kee ac uk
Abstract
We introduce new framework that performs decision decision-making in reinforcement learning (RI.) as an iterative reasoning process. We model agent behavior as the steady-state distribution of parameterized reasoning Markov chain (RMC), optimized with a new tractable estimate of the policy gradient. We perform action selection by simulating the RMC for enough reasoning steps to approach its steady- state distribution. We show our framework has several useful properties that are inherently missing from traditional RL. For instance, it allows agent behavior approximate any continuous distribution over actions by parameterizing the RMC with simple Gaussian transition function. Moreover, the number of reasoning steps to reach convergence can scale adaptively with the difficulty of each action selection decision and can be accelerated by re-using past solutions. Our resulting algorithm achieves state-of-the performance in popular Mujoco and DeepMind Control benchmarks, both for proprioceptive and pixel-based tasks.
1 Introduction
Reinforcement learning (RL) has the potential to provide general and effective solution to many modern challenges. Recently, this class of methods achieved numerous impressive milestones in different problem domains, such games [1I3], robotics [4 and other meaningful real-world applications [7))). However, all these achievements relied on massive amounts of data, controlled environments, and domain-specific tuning. These commonalities highlight some of the current practical limitations that prevent RI. to be widely applicable [TO]
In the deep RL framework, practitioners train agents with the end goal of obtaining optimal behavior. Traditionally, agent behavior is modeled with feed-forward policies gressing from any state to a corresponding distribution over actions. Such formulation yields practical training ob- jectives in both off aff-policy [1]33] and on-policy settings [6. However, we identify three inherent properties of this rigid representation of behavior that could consid- erably impact expressivity and efficiency in continuous control tasks. First, agent behavior is restricted to a class of tractable distributions, which might fail capture the necessary complexity and multi-modality of a task. Sec- ond, the policy performs fixed reasoning process with a feed-forward computation, which potency cannot adapt to the varying complexity of individual action selection problems. Third, decision decision-making is performed every time from scratch, without re- ce-using any past information that might still inform and facilitate the current action selection problem.
( [s)
Q4
42
Q3
S
Depiction agent decision- making with serial Markov chain reasoning.
Figure 1:
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Unlike RL policies, human reasoning does not appear to follow a rigid feed-forward structure. In fact, a range of popular psychological models characterize human focision-makingg as a sequential process with adaptive temporal dynamics [77 Many of these models have found empirical groundings in neuroscience [21]24] and have shown to effectively complement RI. for capturing human behavior in experimental settings 25 26 Partly inspired by these works, we attempt to refiame the deep RL framework by making use of a similar flexible model of agent behavior, in order to counteract its aforementioned limitations.
We introduce serial Markov chain reasoning new powerful framework for representing agent behavior. Our framework treats cerision-making as an adaptive reasoning process, where the agent sequentially updates its beliefs regarding which action execute a series of reasoning steps. We model this process by replacing the traditional policy with parameterized transition function, which defines a reasoning Markov chain (RMC). The steady-state distribution of the RMC represents the distribution of agent behavior after performing enough reasoning for decision-making. Our framework naturally overcomes the aforementioned limitations of traditional RI. In particular, we show that our agent's 's behavior can approximate any arbitrary distribution even with simple parameterized transition functions, Moreover, the required number of reasoning steps adaptively scales with the difficulty of individual action selection problems and can be accelerated by re-using samples from similar RMCs.
To optimize behavior modeled by the steady-state distribution of the RMC, we derive a new tractable method to estimate the policy gradient. Hence, we implement new effective off off-policy algorithm for maximum entropy reinforcement learning (MaxEnt RL)
2 28 named Steady-Stare Policy Gradient (SSPG). Using SSPG, we empirically validate the conceptual properties of our framework over traditional MaxEnt RI. Moreover, we obtain state-of-the-ard results for popular benchmarks from the OpenAl A Gym Mujoco suite 29 and the DeepMind Control suite from pixels 30)
In summary, this work makes the following key contributions:
1. We propose serial Markov Chain reasoning a framework to represent agent behavior that can overcome expressivity and efficiency limitations inherent to traditional reinforcement learning.
2. Based on our framework, we derive SSPG, a new tractable off-policy algorithm for MaxEnt RL.
3. We provide experimental results validating theorized properties of serial Markov Chain reasoning and displaying state-of-the performance on the Mujoco and DeepMind Control suites.
2 Background
2.1 Reinforcement learning problem
We consider the classical formulation of the reinforcement learning (RL) problem setting as a Markov Decision Process (MDP) 311, defined by the tuple (S, A, P. 7) In particular, at each discrete time step the agent experiences a state from the environment's 's state-space, 8t E S, based on which it selects an action from its own action space, a, E A. In continuous control problems (considered in this work), the action space is typically compact subset of an Euclidean space Rdim(A), The evolution of the environment's state through time determined by the transition dynamics and initial state distribution, P and po- Lastly, the reward function represents the immediate level of progress for any state-action tuple towards solving a target task. The agent's behavior is represented by a state-conditioned parameterized policy distribution ne. Hence, its interaction with the environment produces trajectories, T = (50, ag, 81, ST, aT), according to a factored joint distribution Pr, (T) = (o(s)) I Te (s (s) ((s:+1(ss a.). The RL objective is to optimize agent behavior as to maximize the discounted sum of expected future rewards: arg max Ep. (r) ('rss,a)
2.2 Maximum entropy reinforcement learning and inference
Maximum entropy reinforcement learning (MaxEnt RL) +2 considers optimizing agent behavior for a different objective that naturally arises when formulating action selection as an inference problem Following Levine (28). we consider modeling set of binary optimality random variables with realization probability proportional to the exponentiated rewards scaled by the temperature o,
33 B5-36
p(Or|st, at) x exp( rr)( The goal of MaxEnt RL is to minimize the KL-divergence between

---

trajectories stemming from agent behavior, Pmo (T). and the inferred optimal behavior, p(T
log po(so)
DEL (p= (T)))l((((((00)) = Epte())
po(so) exp( ux) P(44))
(1)
T
-p (r)
Σ r(st, + oH
The resulting entropy-regularized objective introduces an explicit trade-off between exploitation and exploration, regulated by the temperature parameter scaling the policy's entropy. An effective choice to optimize this objective is to learn an auxiliary parameterized soft Q-function 37:
(st, 0z) = -Epoo (r)s).a))
r(s), at) + Σ r(ssrae) + all (T((((()))))
(2)
e'=+1
Given some state, (8.)) represents an energy-function based on the expected immediate reward and the agent's future likelihood of optimality from performing any action. Thus, we can locally optimize the MaxEnt objective by reducing the KL-divergence between x and the canonical distribution of its current soft Q-function. This is equivalent to maximizing the expected soft Q-function's value corrected by the policy's entropy, resembling a regularized policy gradient objective [1
arg max Be,a>me(-1s) (*, a) + aH (Ta(a))))]
The policy usually modeled with neural network outputting the parameters of some tractable distribution, such as a factorized Gaussian, (-() N (H)(s);; Es))). This practice allows to efficiently approximate the gradients from Eqn. B via the reparameterization trick BX We consider
the off-policy RL setting, where the agent alternates learning with storing new experience in data
buffer, D. We refer the reader to Haarnoja et al. B B0 for further derivation and practical details.
Policy Gradient with serial reasoning
3.1 Reasoning as a Markov chain
We introduce Serial Markov Chain Reasoning, a new framework model agent behavior, based on conceptualizing action selection an adaptive, sequential process which we refer to as reasoning. Instead of using traditional policy, the agent selects which action to execute by maintaining an internal action-belief and a belief transition (BT-) policy, <' [a, s). During the reasoning process, the agent updates its action-belief for a series reasoning steps by sampling new action with the BT-policy n" taking both environment state and previous belief-belicf input. We naturally represent this process with a reasoning Markov chain (RMC), a discrete-time Markov chain over different aationbbllifss with transition dynamics given by the BT-policy. Hence, for any input environment state and initial action-belief ag, the n-step transition probabilities of the RMC for future reasoning steps 1, 2, defined as:
n. (alao. s) = π (al (a)aa,))m"))) 1) (a')ao, s)da', for n >> 1, and
π
Given compact action space and BT-policy with non-zero infimum density, as the number of reasoning steps grows, the probability any action-belief the RMC converges to some steady-state probability which is independent of the initial action-belief We denote this implicit probability distribution as the steady-stat state (SS-) policy, symbolized by T r(ass):
ensure that
Lemma 3.1. Steady-state convergence. For any environment state 8, consider reasoning Markov chain (RMC) defined on a compact action space A with transition probabilities given by x" Ja. s). Suppose that inf (n (a')aa 8) : a', a',a= E A) > 0. Then there exists a steady-state probability distribu- tion function nt (-|8) such that:
lim Th (alan, 8) - T" (a)s) for all A. n-000
Proof. See Appendix
3

---

Tranation distributions the IIC for state
Emprical steady state distrtuttion of RNC for state
0.10
0.11
Canonical distribution for Q"
Best squashed Gaussian approssmation
1.50
Samples from =1(),
0:04
Srobatbil denstty
3.00
0.11
0.00
0.38
0.00
0.55
actin
0.14
003
Aciion bww.lllaaa.o....
Figure 2: (Left) BT-policy transition probabilities and quantized RMC state diagram. (Right) Sample approximation of related steady-state distribution compared to canonical distribution of the soft Q-function.
The RMC's steady-state probabilities can be interpreted as representing the distribution of agent's s behavior after an appropriate number of reasoning steps are performed. In this work, we strive to op- timize the agent's s behavior following the MaxEnt RL framework described in Section 2 In particular, we consider learning a parameterized BTT-policy, Ty. to produce appropriate transition probabilities for each environment state such that the SS-policy, Tÿ. from the resulting RMC optimizes:
arg max (() = (-11))
[Q,(s,)) a) + add add (TT(())))
(6)
Here, 2% is parameterized soft Q-function for the agent's 's behavior from x", which we learn by minimizing a squared soft Bellman loss utilizing delayed parameters ø' and samples from mz=
arg min J(0) Es,,,s' [(0)(s. (r(s, a) + + BBaool))) [Q' +(((66((1)))) (7)
In Fig. 2 we illustrate the relationship between a learned BT-policy, the corresponding SS-policy, and the soft Q-function in a I I-dimensional toy task (see App. C for details). In this example, the BT-policy parameterized as a simple squashed Gaussian distribution, with unimodal transitions between consecutive action beliefs (Fig. 2 Left). We obtain samples of agent behavior (the SS- SS-policy) by performing a series of reasoning steps, using the BT-pollcy to simulate the RMC until we approach steady-state convergence. By plotting the resulting empirical distribution of agent behavior, we see it closely matches the multi-modal, non-Gaussian canonical distribution from its soft Q-function (Fig. 2 Right). This example shows how the expressive power of agent behavior in our framework can go far beyond the BTT-oolccy' 's simple parameterization, enabling for the effective maximization of complex and multi-modal MaxEnt objectives.
3.2 Learning the belief transition policy
We propose new method to estimate the policy gradient of the BT-policy, Tτ.. for optimizing the steady-state MaxEnt objective described in Section 3.T We note that the gradient from Eq. involves differentiating through an expectation of the steady-state policy, тÿ. However, л is only implicitly defined, and its connection with the actual B BT-policy or its parameters does not have tractable closed-fore form expression. To approach this problem, we introduce family of n-step extensions the soft Q- O-function, Q; S 5 A + IK for n = 0, 1, defined as:
as) = - (a'la, la 2) (s, d' d')da' with VoQu =
(8)
Intuitively, each n-step soft Q-function 2 (s. a) outputs the expected soft Q-value after performing n reasoning steps in the RMC from the initial action-belit a. However, we treat the output of each n-step soft Q-function as being independent of the actual parameters of the BT-policy, 0. Hence, we can interpret computing (i(s a) as simulating the RMC with a fixed and immutable copy of the current T5. We use this definition provide convenient notation in the following new Theorem that expresses the policy gradient without differentiating through -े.
'This is unrelated to the steady state distribution for horiite MDPs considered in prior work !0

---

Theorem 3.2. Steady-state policy gradient. Let ogg. a. s) be parameterized belief transition policy which defines a reasoning Markov chain with a stationary distribution given by the steady-stan state policy (1)). Let Q2 be real function defined on S x A, with a family of n-step extensions (Qa as defined in Eq. 8 Suppose , Q and their gradient with respect to 0 (denoted Vo) are continuous and bounded functions. Then
Ve Ea (s) Ba
lim N No+00
Σ
Vo
B - (2n(s,
(9)
Proof. See Appendix A
approximate the policy gradient expression Eq. 9 with an arbitrarily small expected error using finite number of n-step soft Q-functions, i.e. N (see App. A An intuition for this property follows from the fact that for large enough n, Lemma 3.1 implies that T (ala', (alaa,;) R (a(s) and, thus, (%, a') ss SA (g>((as))( (s, a)da.
Using Lemma steady-state convergence),
Therefore, the value of each Q% as) will be independent of the BTT-policy's 's action a', such that No (nrrs)(()aas)) (s, a')] ~ O. In other words, each subsequent step in the RMC introduces additional randomness that is independent of a', causing a warranted vanishing gradient phenomenon 41 which culminates with converging to zÿ. Using similar notation as Haarnoja et al. (39), we apply the reparameterization trick [X]] to express the BT-pollcy in terms of deterministic function (a e), taking as input Gaussian noise vector e. This allows to rewrite the gradient in each inner expectation in the sum from Eq. Das as:
Ve Eu' waft a.e) (2, ((.1)(( V ao) Vol s,
(10)
where ag (a, s, en). We can apply the same reparameterization for all n-step soft Q-functions, to establish a new relationship between the gradient terms V. Qú (3, an):
Vao (s. Vao / n (an au, S) an dan Vao / x² (r' s)Q2 (s, an da
= E, V ( (an, 8,11)] where, 01 = s(a, 8, 6,).)
(11)
11 we purposefully omit the dependence of f and nh from 0 since each OR term is a local approximation of the RMC that does depend on 0 (as defined in Eq. S. By recursively applying this relationship (Eq.
In Eq.
I to Va, 1= a1) and all subsequent gradient terms we obtain:
V (s) Ees.....n
Van (s
V a. (a, s,
(12)
i=0
where 0; f(aa;11, for I....,n. n. By combining Eq. 10 and Eq. reparameterize and express the whole sum in Eq, 9 as:
12
we can thus
N
Vg En-rs(11) [s) m
Vo E, Ea (s,(s,
n=0
(13)
Σ V (3(s,an))
II i=0
Vold(a,s,co)
Eeg....
Eq. intuitively corresponds to differentiating through each Q (s, a') term by reparameterizing the RMC Hence, to get a sample estimate of the policy gradient we can simulate the reparameterized
RMC for N reasoning steps to obtain a1,..., a,, compute each Q (s, an) term, and backpropagate (e.g., with autealifferentiation)) Following Haarnoja et al. 13
39
we can apply Theorem 3.2 and
easily extend the same methodology to estimate the MaxEnt policy gradient from Eq. g that also
involves extra entropy term. We include this alternative derivation in App. A for completeness.
5

---

Algorithm/ Agent Acting
Algorithm 2 Agent Learning
input: s, current state
input: D, data buffer
ao ~ A
(s, a,,088,. .r)) D
N +4-0
au ~ Ti(-|a,
R" < 4.00
for <- 0, [N] do
while R" > 1.1 do
Q <- (5())an))
D Eq.
aN+1 TT(-[aN) N f N +1
6n+1 N(0, 1),
an+1 = (an, 6++1
VoQ Vo [M] Q.)
T Thm. 3.2
Update Rp with a
b Eq 16
arg ming ((0)
> Eq
+ NÑ (1-
b p (0,1)
a' ~ 9:(NN]
Å - A AlINN
arg min (0)
b Eq.
output: a ~ a1.N
3.3 Action selection and temporal consistency
To collect experience in the environment, we propose to perform reasoning with the BTT-policy starting from a ser of different initial action-beliefs {ağ...., ...; a J. We batch this set as a single input matrix, a0. to make effective use of parallel computation. To reduce the required number of reasoning steps and facilitate detecting convergence to Tă. we identify two desirable properties for the distribution of action-belic in ag. In particular, initial action-beliefs should 1) be likely under xd. and 2) cover diverse modes of T2. Property (1) should logically accelerate reasoning by providing the BT-policy with already-useful information about optimal behavior. Property (2) serves to provide the BT-policy with initial information of diverse behavior, which facilitates convergence detection (Sec. 3.4 and expedites reasoning even if the RMC has slow mixing times between multiple modes. To satisfy these properties, we use a simple effective heuristic based on common eemporal-cossitenny properties of MDPs
Especially in continuous environments, actions tend to have small individual effects, making them likely relevant also for environment states experienced in the near future. Thus, we propose storing past action-belicfs in a fixed sized buffer, called the short-term action memory, A, and use them to construct ag. We find this strategy allows to effeetively regulate the initial action- action-belicfs quality and diversity through the size of Å, accelerating convergence at negligible cost.
2 2
3.4 Detecting convergence to the steady-state policy
A key requirement for learning and acting with BT-policies, as described in Sections 3.2 and 3.3 is the ability to determine sufficient number of reasoning steps (N) for the action-belief distribution to converge. Given the properties of the RMC, there exist different analytical methods that provide a priori bounds on the rate of convergence 4E Ho. However, using any fixed N would be extremely limiting as we expect the BT-poolic and the properties of its resulting RMCs to continuously evolve during training. Moreover, different tasks, states, and initial cetion-belict, might affect the number of reasoning steps required for convergence due to different levels of complexity for the relative decision- making problems. To account for similar conditions, in the Markov Chain Monte Carlo literature, the predominant approach is to perform statistical analysis of the properties of the simulated chain, choosing from several established convergence diagnostic tools [4 employ a similar adaptive strulegy by analyzing the history of the simulated RMC to determine the appropriate number of reasoning steps. Since we apply T from a diverse set of initial action
Hence, we propose to
beliefs (see Section 3.3). , we base our convergence-detectioo strategy on the seminal Gelman-Ruil Rubin
(GR) diagnostic [50 and its multivariate extension [TT]. In particular, the multivariate GR diagnostic
computes the psendo scale reduction factor (PSRF), score representing whether the statistics of multivariate variable of interest have converged to the steady-state distribution. The intuition behind this diagnostic is to compare two different estimators of the covariance for the unknown steady- distribution, making use of either the samples within each individual chain and between all different chains. Thus, as the individual chains approach the true steady-state distribution, the two estimates should expectedly get closer to each other. The PSRF measures this precise similarity based on the largest eigenvalue of their matrix product.
For our use-case, we employ the PSRF to determine the convergence of the set of action-beliefs a1:N; as perform consecutive reasoning steps with z/.. Following [5]], calculate the average sample

---

covariance of the action-beliefs within each of the parallel chains (W) computed from batched set
of initial action-beliefs ag [ap: ay. ... o M1
am 1
Wm=
1
aam
W
1 M
Σ
Wm
(14)
We compare W with an unbiased estimate of the target covariance, constructed from the sample covariance between the different parallel chains (B):
N
M
N
1
á
ag
B=
tamh - -a) -a)².
(15)
N
M
M
n=
#=1
n=1
The PSRF for a is then computed from the largest eigenvalue (Amaz) of the product W- B, as:
R
N + Amaz Smar(W-11 (W-1B)
(16)
Thus, the individual chains approach the distribution of Tÿ. the PSRF (RP) will approach 1. Following Brooks and Gelman [51], we use R < 1.1 as an effective criterion for determining the convergence of a1:N- In practice, steps for convergence, Ñ. We use ['] the number of reasoning steps to simulate the RMC with m
also keep ranning mean of the current number of reasoning
when computing gradients from Eqs. 6 7 [N] is a safe choice to ensure near unbiased optimization since R2 < 1.1 is considered very conservative criterion 52 and we can learn by simulating the RMC from recent actions stored in the data buffer, which are already likely close to optimal.
We provide further details regarding our implementation and its rationale in App. B We provide simplified summary of our adaptive reasoning process for acting and learning in Algs.
3.5 Advantages of serial Markov chain reasoning
Based on the above specification, we identify three main conceptual advantages of our serial Markov chain reasoning framework. Unlimited expressiveness. The distribution of agent behavior given by the SS-policy тÿ. is a mixture model with potentially infimitely many components. Thus, even a simple Gaussian parameterization of the BTT-policy T would make T& a universal approximator
of densities, providing unlimited expressive power the agent [53] 54 2. Adaptive computation.
The number of reasoning steps performed to reach approximate convergence is determined by the properties of each environment state's RMC. Hence, the agent can flexibly spend different amounts of computation time based on the complexity of each action-selection problem, with potential gains in both precision and efficiency. 3. Information reuse. By storing past solutions to similar RMCs, we can initialize the reasoning process with initial action-beliefs that are already close to gÿ. This allows properties of the MDP to exploit traditionally discarded information
using the and accelerate agent reasoning. We provide empirical validation for these properties in Section 4.2
4 Experimentation
4.1 Performance evaluation
We evaluate the serial Markov chain reasoning framework by comparing its performance with current ofate-of-the-art baselines based on traditional RL. We consider 6 challenging Mujoco tasks from Gym 20 56] and 12 tasks pixel-based tasks from the DeepMind Control Suite (DMC) 50 In both settings, we base our implementation on MaxEnt RL, replacing the traditional policy with a Gaussian BT-policy optimized with the training procedures specified in Sec. B Other orthogonal design choices (c.g., network architectures) follow contemporary RL practices, we refer to App. C or the code for full details. We call the resulting algorithm Steady-State Policy Gradient (SSPG).
We report the mean performance curves and aggregate metries using the statistical tools from Rliable 55). In particular, we compare normalized performance profiles [57] interquantile mean (IQM), and probubility of improvements over baselines with the Mann- Whitney U statistic [58]. The reported
ranges/shaded regions represent 95% stratified buotstrap confidence intervals (CIs) 59 In App. D we provide per-task results and further statistical analysis. For each experiment, we collect the returns of SSPG over five seeds, by performing 100 evaluation rollouts during the last 5% of steps.
7

---

OpenAl Gym Mujoco performance evaluation
SSPG
REDQ
MBPO
WPD
SAC220
PISPIG baseline)
IQM
with
Mean performance
SSPG
1.00
1.0
REDQ
0.75
MDPO
0.50
0.5
MBPO
IAP
0.25
REDQ
SAC-20
0.00
0.0
0.45 0.60
0.75
0.90
0.2
0.4
0.6
0.8
0.0
0.5
1.0
0
50
100
150
200
DeepMind Control performance evaluation
SSPG
DrQv2
DrQ
CURL
SAC
PISSPs > baseline) 1:5M
IUM st 1.5M
Frection of runs with score >-t
Kean performance curve
SAC
SSPG
1.00
0.75
CURL
Drov2
0.75
0.50
Dro
0.50
DrŌ
CURL
0.25
0.25
DrQv2
SAC
0.45
0.60
0.75
0.90
0.15 0.30 0.45
0.60
0.75
6.0
0.5
1.0
Figure 3: Performance evaluation of SSPG and recent state-of-the-art baselines using Rliable [55
We consider
six OpenAl Gym Mujoco tasks 20
(Top) and twelve DeepMind Control tasks from pixels 30
(Bottom).
Mujoco suite. We evaluate on challenging set of Mujoco tasks popular in recent literature. We compare SSPG with recent RL algorithms achieving state-of- th- sample-efficiens performance on these tasks, which utilize large critic ensembles and high update-to-data (UTD) ratios. We consider REDQ 600 and MBPO [6]] for state-of-the-e afrt algorithms based on the traditional model-fre and model-based RL frameworks. We also compare with iterative amortized policy optimization (IAPO) [62] in which the agent performs iterative amortization to optimize its policy distribution [63] This procedure for action selection more computationally involved than our agent's reasoning process, as it requires both evaluating the policy and computing gradients at several iterations. Yet, as IAPO is still based on the traditional policy gradient framework, its benefits are solely due to reducing the amorlization gup with an alternative action inference procedure. To ground different results, we also show the performance of the seminal Soft Actor-Critic (SAC) algorithm [39], upon which all considered policy gradient baselines are based on. To account for the additional computational cost of training an agent with serial Markov chain reasoning, we use a UTD ratio that half the other algorithms. On our hardware, this makes SSPG faster than all other modern baselines (see App. D)
Figure (Top) shows the performance results after 100K environment steps. Individual scores are normalized using the performance of SAC after 3M steps, enough to reach convergence in most tasks. SSPG considerably outperforms all prior algorithms with statisticully meaningful gains, as per the conservative Neyman-Pearson statistical testing criterion (64]
Furthermore, SSPG even We obtain similar results evaluating at 50K and 200K steps (App. D) In comparison, IAPO obtains lower performance than other non-iterative basclines while being the most compute-intensive algorithm. This indicates that, for sample-efficiency only reducing the amortization gap beyond direct estimation might not provide significant benefits. Instead, serial Markov chain reasoning's 's improved expressivity and flexibility appear to considerably accelerate learning, yielding state-of-the-an performance in complex tasks.
stochastically dominates all considered state-of-the-art baselines
65
Deep Control suite. To validate the generality of our framework, we also evaluate on a considerably different set of problems: 12 pixel-based DMC tasks. We follow the recent task specifications and evaluation protocols introduced by Yarats et al. [66). We compare SSPG with DrQu2 [66). the current state-of-the- policy gradient algorithm on this benchmark, which employs a deterministic actor and hand-tuned exploration. We also compare with additional basclines that, like SSPG, are based on MaxEnt RL: Dr 677. CURL 68 and convolutional version of SAC (3)
Figure 3 (Bottom) shows the performance results after 1.5M environment steps. DMC tasks yield returns scaled within set range, [0. 1000], which we use for normalization. Remarkably, also in this domain, SSPG attains state-of-the-ar performance with statistically significant improvements over all baselines. Unlike for the Mujoco tasks, the other considered algorithms based on MaxEnt RL underperform as compared to the deterministic DrQv2, a result Yarats et al. [66] attributed to ineffective exploration. In contrast, SSPG yields performance gains especially tasks where the other baselines struggle (see App. D). These results validate the scalability of our framework to nigh-dimensional inputs and its ability to successfully complement MaxEnt RL.
sparser reward
8

---

0.00
Humanoid v2 performance
quadruped, jun performance
0.30
0045
0.50
-0.75
-0.90
0.25
0.01
-1.20
100
150
200
Gaussaan policy 1o0 ctepe)
Floe policy 130 mape
Seria MC massning 110 shpp)
Goss
Hean sieps IMMC consargence lask (f0
D)
SSPG (rousing recont actions. Ag-A)
Random de
DNC
Humanoid-42 reas, steps
quadiruedd juun reas. steps
12.5
10
10.0
5.0
150
200
Figure 4: (A) Samples visualizations for learned policies in positional bandits of increasing complexity. (B) Mean number reasoning steps required to reach convergence in each task with SSPG. (C) Mean performance ablating the adaptive strategy for detecting reasoning convergence and using fixed numbers of steps. (D) Number of reasoning steps throughout training with and without reusing recent actions as initial action-beliefs.
4.2 Properties of serial Markov chain reasoning
We test if theorized benefits of our framework (Sec. 3.5 hold in practical settings with deep networks and stochastic optimization. We provide further ablation studies and analysis of SSPG in App.
1. Policy expressiveness. First, we test the expressiveness of the behavior learned with SSPG using a Gaussian BT-policy. We design series of single-step toy RL problems where the agent needs to position itself on a small 2D environment with a reward function based on unknown goal locations, which name positional bandits (see App. C for details). The objective of these experiments is to isolate how our framework compares with traditional policies for MaxEnt RI. to explore the environments and learn match the true canonical distributions of returns. As displayed in Fig. f A, even in highly modal positional bandits, the SS SS-policy successfully learns to visit all relevant goals with similar frequencies. Furthermore, quantizing the state space around the goals reveals that the relative RMC intuitively learns to transition between action-beliefs that visit the different goals as reasoning progresses, with a transition matrix matching a cyclic permutation (App. F In comparison, a squashed Gaussian policy expectedly fails to capture the complexity of the canonical distribution, with samples either collapsing to a single mode or covering large suboptimal parts of the action space. We also show results for policy based on normalizing flows 66 I70,, modeled with deep expressive network (App- C After several attempts, we find these models require orders of magnitude more training iterations and data to learn any behavior that is more complex than uni-modal distribution. Yet, even after increasing training by factor of 1000, we still observe the flow policy distribution collapsing in the more complex positional bandits. We attribute our findings to training inefficiencies from lack of proper inductive biases for flow models in the non i.i.d. RL problem setting (71). In particular, flows can assign arbitrarily low probability mass to some regions of the action space, initial local optima can greatly hinder future exploration, exacerbating coverage of the data buffer distribution in vicious circle.
Policy adaptivity. Second, we examine the adaptivity of our framework for tackling decision- making problems with different complexities. We compare the average number of reasoning steps (N) performed by SSPG for each task from Sec. 4. (Fig. B). We identify a general correlation between task difficulty and reasoning computation, with complex robotic manipulation and humanoid locomotion problems requiring the most steps. By concentrating on two representative tasks, we validate the effectiveness of the reasoning process and our adaptive convergence detection strategy with an ablation study where we train SSPG using a fixed number of reasoning steps Nyi E {1, [N), [3N]]- For the case Nfir = 1, which closely resembles traditional RL, we use double the UTD ratio to improve performance and offset any training-time gains from multi-step reasoning. As shown in Fig. C., increasing Nftr yields clear performance improvements, validating that agents can greatly benefit from performing longer reasoning processes. Furthermore, our adaptive SSPG

---

attains the same performance as Nú = [3N] and visibly outperforms Nÿir = [M]. These results show how different action selection problems require different amounts of reasoning computation and validate the practical effectiveness of our adaptive strategy to detect steady-state convergence. We obtain analogous findings for additional tasks and values of N in App.
3. Solution reuse. Last, we examine the effects of the short-term action memory buffer (A) to sample initial action beliefs (ao) in two tasks. We evaluate ablating Å, randomly re-initializing ag from uniform distribution. While there are only minor differences performance-wic between the two approaches (App. F. sampling ag from the short-term action memory considerably decreases the number of reasoning steps for convergence (Fig. D). Moreover, observe the gap in reasoning efficiency expands throughout training as the agent's 's steady behavior further improves for the target task. This result validates that simple temporal heuristic can provide considerable efficiency benefits, amortizing the additional computational cost of our powerful new framework.
5 Related work
There have been several prior attempts to extend ubiquitous Gaussian policies 13
3
with simple normalizing flows 39 70,, both to improve expressiveness 774 75 and to instantiate behavior hierarchies 76]. Yet, the expressiveness of normalizing flows is coupled with some training challenges [ZI], which we show can lead to premature convergence to suboptimal solutions in RL (Sec. 4.2 Other works also considered entirely replacing policy models with gradient- 4 or gradient-based optimization over the predicted values 777 Marino et al. [62) similarly considered learning an optimizer to infer Gaussian behavior 28 with iterative amortization (5) However, while all these works consider alternative modeling of agent behavior, they are still based on the traditional RL framework of representing decision-making as the output of a fixed process. Instead, our work entails a conceptually different approach and enables implicit modeling of agent behavior as the result of an adaptive reasoning process, orthogonally providing agents also with additional flexibility to scale computation based on the properties of cach individual input state.
Outside RL, there have been efforts to model generation processes with parameterized Markov chains learned to revert fixed noise injection processes acting on data 778 x2 Based on this framework, diffusion models [83 recently achieved remarkable results for image generation 85 86). While applied to inherently different problem settings, these works share some conceptual resemblances with our framework and highlight the vast scaling potential of implicit modeling.
Conclusion
We introduced serial Markov chain reasoning, a novel framework for modeling agent behavior in RL with several benefits. We showed our framework allows an agent to 1) learn arbitrary continuous action distributions, 2) flexibly scale computation based on the complexity of individual action- selection decisions, and 3) re-use prior solutions to accelerate future reasoning. Hence, we derived SSPG off- aff-policy maximum entropy RL algorithm for serial Markov chain reasoning, achieving state-of-the-art performance on two separate continuous control benchmarks. While for problems with discrete action spaces simple multinomial policy distributions already provide unlimited expressivity, we note that the inherent computational adaptivity of our framework could still yield benefits over traditional fixed policies in these settings. Furthermore, we believe our motivation and early results provide a strong argument for the future potential of serial Markov chain reasoning, even beyond off-policy RL and simulation tasks. We provide our implementation for transparency and facilitate future extensions at siiess. wwwgge.oog...ooooooooooooo...... moogle.com/vin www.///vwww//eeaall....mmm
Acknowledgments
We thank Johannes Lutzeyer for providing valuable feedback on an earlier draft of this work. Edoardo Cetin would like to acknowledge the support from the Engineering and Physical Sciences Research Council [EP/R513064/11
Oya Celiktutan would also like to acknowledge the support from the LISI Project, funded by the Engineering and Physical Sciences Research Council [EP/VO10875/1]. Furthermore, we thank Toyota Motor Europe and Toyota Motor Corporation for providing support towards funding the utilized computational resources.
10

---

References
[1] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013.
[2] David Silver. Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint (rXiv:/712.018/1 2017.
[3] Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grand- master level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782): 350-354, 2019.
[4] Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, al. Qt-opt: Scal- able deep reinforcement learning for vision-based robotic manipulation. arXiv preprint arXiv:1806. 10293, 2018.
[5] OpenAL, Ilge Akkaya, Marcin Andrychowicz, Maciek Chociej, Mateusz Litwin, Bob McGrew, Arthur Petron, Alex Paino, Matthias Plappert, Glenn Powell, Raphael Ribas, Jonas Schneider, Nikolas Tezak, Jerry Tworek, Peter Welinder, Lilian Weng. Qiming Yuan, Wojciech Zaremba, and Lei Zhang. Solving rubik's 's cube with robot hand. CoRR. abs/1910.071 2019.
[6] Alex X Lee, Coline Manon Devin, Yuxiang Zhou, Thomas Lampe, Konstantinos Bousmalis, Jost Tobias Springenberg, Arunkumar Byravan, Abbas Abdolmaleki, Nimrod Gileadi, David Khosid, et al. Beyond pick-and-place: Tackling robotic stacking of diverse shapes. In 5th Annual Conference on Robot Learning, 2021.
[7] Marc G Bellemare, Salvatore Candido, Pablo Samuel Castro, Jun Gong, Marlos C. Machado, Subhodeep Moitra, Sameera S Ponda, and Ziyu Wang. Autonomous navigation of stratospheric balloons using reinforcement learning. Nature, 588(7836):77-82, 2020.
[8] Jonas Degrave, Federico Felici, Jonas Buchli, Michael Neunert, Brendan Tracey, Francesco Carpanese, Timo Ewalds, Roland Hafner, Abbas Abdolmaleki. Diego de Las Casas, al. Magnetic control of tokamak plasmas through deep reinforcement learning. Nature, 602(7897): 414 $14,419,4 2022.
[9] Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang. Derek Pang, Rene Claus, Ching-Han Chiang, et al. Muzero with self- competition for rate control in vp9 video compression. arXiv preprint arXiv:2202.0m 066266 2022.
[10] Gabriel Dulac-Arold, Daniel Mankowitz, and Todd Hester. Challenges of real-world rein- forcement learning. arXiv preprint arXiv: 190.. 2019.
[11] David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. 2014.
[12] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint
2015.
[13] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 1861-1870. PMLR, 10-15 Jul 2018. URL https://procceddnng
mlr. www.s/rssssveee va0/sss/vv//// pttpp///////aaaaaaaaaaaaa3/. hatml.mmmmlall.l...1.
[14] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lilli- crap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928-1937, 2016.
[15] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. CoRR, abs/ 7707.06347
2017. URI. httt:://arxii http//axvvvvor..... orgg//

---

[16] Karl W Cobbe, Jacob Hilton, Oleg Klimov, and John Schulman. Phasic policy gradient. In International Conference on Machine Learning, pages
PMLR, 2021.
[17] AR Pike. Stochastic models of choice behaviour: response probabilities and latencies of finite markov chain systems 1. British Journal of Mathematical and Statistical Psychology, 19(1)
15-32, 1966.
[18] Roger Ratcliff. A theory of memory retrieval. Psychological review, 85(2):59, 1978.
[19] Marius Usher and James L McClelland. The time course of perceptual choice: the leaky,
competing accumulator model. Psychological review, 108(3):550, 2001.
[20] Scott D Brown and Andrew Heathcote. The simplest complete model of choice response time: Linear ballistic accumulation. Cognitive psychology, 57(3):153-178, 2008.
[21] Joshua Gold and Michael N Shadlen. Neural computations that underlie decisions about sensory stimuli. Trends in cognitive sciences, 5(1) 5(1):10-16, 2001.
[22] Leendert van Maanen, Scott Brown, Tom Eichele, Eric-Jan Wagenmakers, Tiffany Ho, John Serences, and Birte U Forstmann. Neural correlates of trial-to-trial fluctuations in response caution. Journal of Neuroscience, 31(48):17488 17495, 2011.
[23] Sebastian Gluth, Jörg Rieskamp, and Christian Büchel. Deciding when to decide: variant sequential sampling models explain the emergence of value-based decisions in the human brain. Journal of Neuroscience, 32(31): 16686-199886, 2012.
[24] Leendert Van Maanen, Laura Fontanesi, Guy E Hawkins, and Birte U Forstmann. Striatal activation reflects urgency in perceptual decision making. Neuroimage, 139:294 303, 2016.
[25] Mads Lund Pedersen, Michael J Frank, and Guido Biele. The drift diffusion model as the choice rule in reinforcement learning. Psychonomic bulletin & review, 24(4):1234-125) 2017.
[26] Laura Fontanesi, Sebastian Gluth, Mikhail Spektor, and Jörg Rieskamp. A reinforcement learning diffusion decision model for value-based decisions. Psychonomic bulletin & review, 26(4): 2019.
[27] Brian D Ziehart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. 2010.
[28] Sergey Levine. Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv preprint arXiv: /805.00099 2018.
[29] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym. arXiv preprint arXiv: /606 01540, 2016.
[30] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et Deepmind control suite. arXiv preprint 1000000801.00090, 2018.
[31] Richard Bellman. markovian decision process. Indiana Univ. Math. J., 6:679-684, 1957.
ISSN 0022-2518.
[32] Brian D Ziebart, Andrew Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. 2008
[33] Hagai Attias. Planning by probabilistic inference. In International Workshop on Artificial Intelligence and Statistics, pages 9-16. PMLR, 2003.
[34] Emanuel Todorov. General duality between optimal control and estimation. In 2008 47th IEEE Conference on Decision and Control, pages 4286-4292. IEEF, 2008.
[35] Mare Toussaint and Amos Storkey. Probabilistic inference for solving discrete and continuous state markov decision processes. In Proceedings of the 23rd international conference on Machine learning, pages 945-952, 2006.
[36] Brian D Ziebart, Andrew Bagnell, and Anind K Dey. Modeling interaction via the principle of maximum causal entropy. In ICML, 2010.
[37] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference Machine Learning, pages 1352-1361. PMLR, 2017.
[38] Diederik Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
12

---

[39] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta. Pieter Abbeel, al. Soft actor-critic algorithms and applications. arXiv preprint /r/iv:/8/2.0000
2018.
[40] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA, 2018. ISBN 0262039249.
[41] Yoshua Bengio, Patrice Simard, and Paolo Frasconi. Learning long-term dependencies with gradient descent is difficult. IEEE transactions on neural networks, 5(2):157-166, 1994.
[42] Sahil Sharma, Aravind S Lakshminarayanan, and Balaraman Ravindran. Learning to repeat: Fine grained action repetition for deep reinforcement learning. arXiv preprint arXiv:/702.0603 2017.
[43] Will Dabney, Georg Ostrovski, and André Barreto. Temporally-extendeed (repsilon--greedde exploration. arXiv preprini arXiv:2006.077 01782, 2020.
[44] Jeffrey S Rosenthal. Minorization conditions and convergence rates for markov chain monte carlo. Journal of the American Statistical Association, 90(430):558-566, 1995.
[45] Peter H Baxendale. Renewal theory and computable convergence rates for geometrically ergodic markov chains. The Annals of Applied Probability, (5(1)))700 2005.
[46] Christophe Andrieu, Gersende Fort, and Matti Vihola. Quantitative convergence rates for subgeometric markov chains. Journal of Applied Probability, 52(2):391 2015.
[47] Mary Kathryn Cowles and Bradley P Carlin. Markov chain monte carlo convergence diagnos- ties: a comparative review. Journal of the American Statistical Association, 91(434):883-904, 1996.
[48] Stephen P Brooks and Gareth O Roberts. Assessing convergence of markov chain monte carlo algorithms. Statistics and Computing, 8(4):319-3355 1998.
[49] Vivekananda Roy. Convergence diagnostics for markov chain monte carlo. Annual Review of Statistics and Its Application, 7:387 01277-41,220 2020.
[50] Andrew Gelman and Donald Rubin. Inference from iterative simulation using multiple sequences. Statistical science, 7(4):457-472, 1992.
[51] Stephen P Brooks and Andrew Gelman. General methods for monitoring convergence of iterative simulations. Journal of computational and graphical statistics, 7(4):434 455, 1998.
[52] Dootika Vats and Christina Knudson. Revisiting the gelman-rubin diagnostic. Statistical Science, 3684)5518-529, 2021.
[53] D Michael Titterington, Smith Afm, Adrian FM Smith, UE Makov, et al. Statistical analysis of finite mixture distributions, volume 198. John Wiley & Sons Incorporated, 1985.
[54] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
[55] Rishabh Agarwal, Max Schwarzer, Pablo Samuel Castro, Aaron C Courville, and Marc Bellemare. Deep reinforcement learning at the edge of the statistical precipice. Advances in Neural Information Processing Systems, 34, 2021.
[56] Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026-5033, 2012. doi: 10. 109/TOOS 221.2022222222 2.6661099
[57] Elizabeth D Dolan and Jorge J Moré. Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201-213, 2002.
[58] H. B. Mann and D. R. Whitney. On Test of Whether one of Two Random Variables is Stochastically Larger than the Other. The Annals of Mathematical Statistics, 18(1):50
60, 1947, doi: 10. 00.1214/aom//117773000
URL https://aoi.org//10 12140///.111//mmmm
1177730491
[59] Bradley Efron. Bootstrap methods: another look at the jackknife. In Breakthroughs in statistics, pages 569-593. Springer. 1992.
[60] Xinyue Chen, Che Wang, Zijian Zhou, and Keith Ross. Randomized ensembled double q-learning: Learning fast without model. arXiv preprint arXiv:2101 2021.
13

---

[61] Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. In Advances in Neural Information Processing Systems. 2019.
[62] Joseph Marino, Alexandre Piché, Alessandro Davide lalongo, and Yisong Yue. Iterative amortized policy optimization. Advances in Neural Information Processing Systems, 34, 2021.
[63] Joe Marino, Yisong Yue, and Stephan Mandt. Iterative amortized inference. In International Conference on Machine Learning, pages 3403-3412. PMLR, 2018.
[64] Xavier Bouthillier, Pierre Delaunay, Mirko Bronzi, Assya Trofimov, Brennan Nichyporuk, Justin Szeto, Nazanin Mohammadi Sepahvand, Edward Raff, Kanika Madan, Vikram Voleti, et al. Accounting for variance in machine learning benchmarks. Proceedings of Machine Learning and Systems, 3:747-769, 2021.
[65] Rotem Dror, Segev Shlomov, and Roi Reichart. Deep dominance-hon how to properly compare deep neural models. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2773-2785, 2019.
[66] Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Mastering visual continuous control: Improved data-augmented reinforcement learning. In International Conference on Learning Representations, 2022. URL
wtwplewwwee//eeeee net/forum?id= _SJ-_
yyea8
[67] llya Kostrikov, Denis Yarats, and Rob Fergus. Image augmentation is all you need: Regu- larizing deep reinforcement learning from pixels. In International Conference on Learning Representations. 2021.
[68] Michael Laskin, Aravind Srinivas, and Pieter Abbeel. CURL: Contrastive unsupervised representations for reinforcement learning, In Proceedings of the 37th International Conference on Machine Learning, 2020.
[69] Esteban G Tabak and Cristina V Turner. A family of nonparametric density estimation algorithms. Communications on Pure and Applied Mathematics, 66(2):145-16) 164, 2013.
[70] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint arXiv: 008,08803, 2016.
[71] Ivan Kobyzev, Simon JD Prince, and Marcus A Brubaker. Normalizing flows: An introduction and review of current methods. IEEE transactions on pattern analysis and machine intelligence,
43(11))3964-33)) -3999, 2020.
[72] Abbas Ahdolmaleki, Jost Tobias Springenberg, Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. International Conference on Learning Representations, 2018
[73] Alex X Lee, Anusha Nagabandi. Pieter Abbeel, and Sergey Levine. Stochastic latent actor-critic: Deep reinforcement learning with latent variable model. arXiv preprint arXiv:1907.00953, 2019.
[74] Yunhao Tang and Shipra Agrawal. Boosting trust region policy optimization by normalizing flows policy. arXiv preprint 18Xiv 2018.
[75] Bogdan Mazoure, Thang Doan, Audrey Durand, Joelle Pineau, and R Devon Hjelm. Leveraging exploration in off-policy algorithms via normalizing flows. In Conference on Robot Learning. pages 430-444 PMLR, 2020.
[76] Tuomas Haarnoja, Kristian Hartikainen, Pieter Abbeel, and Sergey Levine. Latent space policies for hicrarchical reinforcement learning. In International Conference on Machine Learning, pages 1851-1860. PMLR, 2018.
[77] Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International Conference Machine Learning, pages 1352-1361. PMLR, 2017.
[78] Yoshua Bengio, Li Yao, Guillaume Alain, and Pascal Vincent. Generalized denoising auto- encoders as generative models. Advances in neural information processing systems, 26. 2013.
[79] Guillaume Alain, Yoshua Bengio, Li Yao, Jason Yosinski, Eric Thibodeau-Laufes Saizheng Zhang, and Pascal Vincent. Gsns: generative stochastic networks. Information and Inference: A Journal of the IMA, 5(2):210-249, 2016.
14

---

[80] Florian Bordes, Sina Honari, and Pascal Vincent. Learning to generate samples from noise through infusion training. arXiv preprint arXiv: nane::773007..3 2017.
[81] Anirudh Goyal, Nan Rosemary Ke, Surya Ganguli, and Yoshua Bengio. Variational walkback: Learning transition operator as a stochastic recurrent net. Advances in Neural Information Processing Systems, 30, 2017.
[82] Erik Nijkamp, Mitch Hill, Song-Chun Zhu, and Ying Nian Wu. Learning non-convergent non-persistent short-run meme toward energy- model. Advances in Neural Information Processing Systems, 32, 2019.
[83] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep un- supervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265 PMLR, 2015.
[84] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in Neural Information Processing Systems, 32, 2019.
[85] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 33:6840-688 68511, 2020.
[86] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis.
Advances in Neural Information Processing Systems, 34, 2021.
[87] Steven Orey. Limit theorems for Markov chain transition probabilities. Nostrand London, 1971.
[88] Esa Nummelin. General irreducible Markov chains and non-negative operators. Number 83. Cambridge University Press, 2004.
[89] Gareth O Roberts and Jeffrey S Rosenthal. Small and pscudo-small sets for markov chains. Stochastic Models, 17(2):121-144 121-145, 2001.
[90] Esa Nummelin. General irreducible Markov chains and non-negative operators. Number 83. Cambridge University Press, 2004.
[91] G Ch Pflug. Gradient estimates for the performance of markov chains and discrete event processes. Annals of Operations Research, 39(1):173-194, 1992.
[92] Bernd Heidergott, Arie Hordijk, and Heinz Weisshaupt. Measure-valuee differentiation for stationary markov chains. Mathematics of Operations Research, 31(1):154-172, 2006.
[93] Tom Rainforth, Rob Comishh Hongseok Yang. Andrew Warrington, and Frank Wood. On nesting monte carlo estimators. In International Conference on Machine Learning, pages 4267-4276 PMLR, 2018.
[94] Don McLeish. A general method for debiasing a monte carlo estimator. Monte Carlo methods and applications, 17(4):301-315 2011.
[95] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521(7553):
436 444, 2015.
[96] Vassili Nestoridis and Vangelis Stefanopoulos. Universal series and approximate identities. Technical report, Technical Report TR-28-2007. Department of Mathematics and Statistics 2007.
[97] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 6980, 2014.
[98] Edoardo Cetin and Oya Celiktutan. Learning pessimism for robust and efficient off-policy reinforeement learning. arXiv preprint arX0v:2110.03375, 2021.
[99] Johan Bjorck, Carla P Gomes, and Kilian Q Weinberger. Towards deeper deep reinforcement learning. arXiv preprint arXiv:2 151, 2021.
[100] Scott Fujimoto, Herke van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In ICML, pages 1582-1591, 2018. htR.itttpp//prrrceeiings mlr
press/v80/fuj wtw:://ffiimmooof... imoiiiia.a....... html
[101] Durk Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, and Max Welling. Improved variational inference with inverse autoregressive flow. Advances in neural informa- tion processing systems, 29, 2016.
15

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section for the derivation of our new framework and Section for empirical evaluation.
(b) Did you describe the limitations of your work? [Yes] We describe limitations related our implementation in Sections [ and of the Appendix. We also discuss limitations related computational costs in Section of the Appendix.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section G of the Appendix.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Section Appendix.
A of
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material and instructions in the supplementary material of our submission. We will provide a link open-sourced implementation at sisittss.... siiess.ooggl wtt.cooo/iiiiee htmm//iiee//rrraammmrt
URL)? [Yes] We include code
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section gof
of the Appendix.
(c) Did you report error bars (c.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section of the Appendix. assets...
4. If you using existing assets (e.g., code, data, models) curating/releusing
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] We include the licenses with the supplementary material.
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "hFCvLvNAmLs", "reviewer": "Reviewer_ZW89", "summary": "This paper introduces a new serial markov chain reasoning for representing agent behavior. Instead of using a policy, the agent selects an action by maintaining an action-belief and a belief transition policy. The authors derive a steady state policy gradient algorithm for estimating the belief transition policy in a MaxEnt RL environment. In addition, this paper also provide a method to determine the number of reasoning steps dynamically. Finally, some empirical experiments are presented to verify the performance of the proposed method in real applications. ", "questions": "I have several questions. The authors state that the proposed reasoning Markov chain is more general compared to the traditional policy. And in the first section, you mentioned that the agent’s behavior can approximate any arbitrary distribution with simple parameterized transition functions.  I don’t fully get this point from the theoretical analysis. Is it true that a parameterized belief transition function can approximate any policy? Can you elaborate your statement a bit by referring to the theorems in the paper?\nAnd since you are using the stationary distribution of a markov chain to define the action, you assumed that the markov chain is ergodic and every action is reachable in every state. I suggest the authors explain the assumptions first before presenting the method and theorems. \n", "limitations": "Yes. The authors adequately addressed the limitations. ", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This method presented in this paper is novel. It has a potential to solve some RL problems in a more expressive way. The idea of learning the action belief instead of the policy makes sense to me. The proof of the theorems is rigorous and looks right to me. The experiments presented in this paper are sufficient and well-designed. The results look promising as the SSPG algorithm outperforms others with significant gains. \n\nWeakness: This paper is a bit hard to follow since some background knowledge is not clearly presented. Before you introduce how to apply the techniques, it is better to have a comprehensive description for them. \n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Yn25URGOoi0", "reviewer": "Reviewer_Mb6P", "summary": "This paper proposes a novel framework for representing decision making in an RL problem as an iterative reasoning process based on serial Markov chains. The authors derive a policy gradient theorem for their framework in the standard RL setting, as well as the MaxEnt RL setting. The empirical evaluation shows improved performance in both state and pixel observations and demonstrates the expressivity of the proposed policy representation.\n", "questions": "My major question is regarding the point discussed in the weaknesses. I have noted it here for easier reference. The rest of the questions are mostly minor comments/suggestions. \n\n1. Can you clarify equation (8) and explain why $\\nabla_\\theta Q_n^s(s, a) = 0$. I am not convinced by the argument of the local approximation, as detailed above. \n2. I suggest the authors give titles to the theorems for better clarification and better guidance of the reader. An inexperienced reader may be lost within the heavy math.\n3. The parameterization of the policy is sometimes written (denoted as $\\pi_\\theta^b$) and sometimes dropped (denoted as $\\pi^b$ or $\\pi^s$). This can confuse and mislead the reader. \n4. This is for my curiosity and I was not expecting to find this answer in the paper. Can recurrent neural networks be used to parameterize the RMC? I believe prior work has made the connection between RNNs and Markov chain reasoning.\n5. Figure 1 is a very generic figure without giving much information about the method. I suggest the authors reconsider that and replace it with something more specific to their work. \n6. The colors and font size on Figure 2 makes the text hard to read.\n", "limitations": "Yes, the authors have addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a solid paper with a clear and interesting idea, novel contribution, and a series of thoroughly conducted evaluations. I, however, have certain concerns regarding one of the key equations / definitions used by the authors which is the basis for all of the main derivations. \n\n## Strengths\n\n### 1. Novelty\nThe proposed method for obtaining policy gradients using serial Markov chain reasoning is novel, to the best of my knowledge. Furthermore, I believe the contributions are significant and relevant as the proposed framework is a core development of RL algorithms and can be potentially impactful. \n\n### 2. Empirical Soundness\nThe empirical evaluation is thorough and sound. In particular, I appreciate using Rliable metrics and comparison against several strong baselines for both state and pixel observations. Finally, several ablation studies are conducted in Appendix E to shed more light onto the method and its hyperparameters.\n\n### 3. Demonstration of useful properties of the proposed method\nI greatly appreciate section 4.2 and correspondingly Appendix F. I have found the empirical results on policy expressiveness and adaptivity to be very convincing and a nice divergence from the standard comparison in the (deep) RL community that is usually concerned only with pure performance. Nevertheless, I do appreciate that the proposed method is outperforming SOTA algorithms.\n\n## Weaknesses\n\n### 1. Theoretical soundness\nI have carefully checked the proofs of Lemma 3.1 and Theorem 3.2 and I acknowledge that the math is correct and sound (based on my understanding) **if** one agrees with the fact that $Q_n^s(s, a)$ is not a function of policy parameters $\\theta$. However, I am not convinced this is the case. The concerning equation is equation (8) in which the authors define: \n$$\nQ_n^s(s, a) = \\int_A \\pi_n^b(a’|a,s) Q_\\phi^s(s, a’)da’,     \\text{   with    } \\nabla_\\theta Q_n^s(s, a) = 0\n$$\nFirst, I am confused with the **\"with\"** statement; is that an assumption, condition, or a result of the definition of $Q_n^s(s, a)$? Second, in L416 of Appendix, the authors write “[since] $Q_n^s(s, a)$ is a local approximation of the RMC with no dependence from $\\theta$...” and continue the proof without again stating why that is the case. \n\nMy understanding is that the $\\pi_\\theta^b$ is paremetrized by $\\theta$, hence $\\pi_n^b$ is also a function of $\\theta$ based on equation (4). In that case, I am interested to know why differentiating equation (8) does not yield the following result which is clearly non-zero: \n\n$$ \\nabla_\\theta Q_n^s(s, a) = \\int_A \\nabla_\\theta \\pi_n^b(a' | a, s) Q_\\phi^s(s, a') da' +  \\pi_n^b(a' | a, s) \\nabla_\\theta  Q_\\phi^s(s, a') $$\n\nGiven that equation (8) is the key for all the consequent derivations, including the main theoretical result of the paper, I am concerned with the theoretical soundness of the paper. \n\nNote: With that said, I am hopeful that this is just a misunderstanding from my side and I am looking forward to hearing the authors’ response to elaborate and clear the confusion. Unfortunately for this reason, my rating is relatively low depite my acknowledgment of the strengths of the work. But I am eagerly looking forward to increasing it if the authors can explain the reasoning behind $\\nabla_\\theta Q_n^s(s, a) = 0$.\n\n**Update after the rebuttal:** I acklowledge that I have been convinced by the argument of the authors and have increased my score from 6 (weak accept) to 7 (accept).\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "P7kg3qsXkOz", "reviewer": "Reviewer_NxbF", "summary": "This paper considers policies expressed as a reasoning Markov chain over actions in the current state that refines its choice of actions until arriving at a steady-state distribution over actions. In this framework the authors learn the number of steps to take before outputting an action and outline a policy gradient theorem that can be leveraged to differentiate through this process. The reason for learning this kind of policy seems to be in order to increase the expressiveness of distributions with multiple modes in the case of continuous action spaces. The authors present experiments demonstrating superior performance to baselines in 6 MuJoCo and 12 DMLab continuous control domains. ", "questions": "- Can you compare what is achieved by your approach more directly to normalizing flows? The main advantage I understood from the related work section is allowing for a dynamic amount of computation. Am I missing something? Can there be an empirical comparison with normalizing flows? \n- What are the “mild assumptions” used in the proof of Lemma 3.1? Even looking through the proof in the appendix, it is not 100% clear to me what these assumptions are. Based on my experience with the Markov chain literature I was expecting something related to stochasticity of transitions or irreducibility and aperiodicity of the Markov chain etc. \n- Can you elaborate more about how information reuse is a benefit of this framework? It seems more like a necessity to make it practical? Is this meant in comparison with normalizing flows?  ", "limitations": "It seems that the authors mostly highlight value in their work with respect to continuous action space domains. Could this approach also provide value in domains with discrete action spaces?", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- The authors propose an adaptive iterative reasoning process with the goal of allowing for more complex multi-modal action space distributions for problems with continuous action spaces.\n- The authors compare to a solid set of baselines across 6 mujoco domains and 12 DMLab domains while also providing nice qualitative experiments and relevant ablation experiments. \n- The approach is a bit outside the box from recent research with the fact that it works well striking me as somewhat surprising on the surface. \n- The derivation of Theorem 3.2 seems involved beyond the standard policy gradient derivation.\n\nWeaknesses: \n- The authors only provide an intuitive rationale for their proposed strategy, on the surface it seems a bit weird to iteratively update actions in this way. I understand that it makes the distribution more expressive, but it is not clear to me why this direction is preferable to normalizing flows or some adaptive version of normalizing flows. \n- \"Steady-state policy gradient\" is a confusing term in light of the RL literature. I get what you mean upon reading, but it is confusing with the policy gradient for continuing environments which is defined over a different steady-state distribution (i.e. Sutton and Barto, 2018 Section 13.6). \n- It would be nice to provide readers with more information regarding how convergence to the steady-state distribution was determined for those not familiar with pseudo scale reduction factors. ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LfBwxdNKKKJ", "reviewer": "Reviewer_8GHv", "summary": "The paper proposes a family of implicitly defined stochastic policies that arise as the steady-state distribution of a Markov Chain whose transition function is a neural net which takes an action, a system state and a noise vector and produces a new action. The authors motivate this family of policies in three ways: a) they can approach any distribution over the action space b) the computation required to plan an action can vary depending on the state c) planning can be shortened by initializing the Markov chain with recently used actions, which can be seen as a form of solution re-use. The method improves over all considered baselines in typical benchmarks.", "questions": "### Questions\n\n* In eq. 13, the gradient term contains a product of gradients over the reasoning steps. Do the usual concerns about vanishing/exploding gradients apply here? Did you observe instability in practice?\n\n* What is the real-time capability of these policies (in terms of deployment after training)?", "limitations": "These points are addressed well, aside from my comments above about computation time at deployment.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* The idea reminds me of things like deep equilibrium models, but I believe the specific form here might have an advantage over those (stochasticity). I certainly haven't seen this type of model applied to RL, and I found it quite interesting.\n* The paper has a good flow. Ideas, derivations and results are presented in a way that can be followed easily. Steps that would be complicated to parse at first reading are relegated to the appendix, which is good.\n* The experimental results are both thorough and equivocally in favor of the model.\n* The paper presents ablations that support the motivation for using a policy that refines itself over multiple steps (beyond that of improved performance). The experiments on simple positional bandits show that the model has an easier time accommodating multi-model distributions compared to normalizing flows, which would be the go-to model for something like this (aside from mixture density networks perhaps). Figure 4 b) and d) support the intuitions about multi-step reasoning. In OpenAI-Gym, Humanoid requires the most reasoning steps, while pendulum requires the least for instance. Re-using recent actions seems to bring an overall reduction in the number of reasoning steps, which is another thing that checks out.\n\n### Weaknesses\n\n* I believe the core weakness of the paper is the increase in computation. The authors analyze this point in terms of training time. I believe it should also be analyzed in terms of the cost of acting during deployment. How many times per second can we query such a policy? This remains somewhat unaddressed. I think it would also be interesting to compare SSPG to the other baselines in terms of the number of reasoning steps that are used (at the end of training, if we allow SSPG to be trained the usual way). At how many steps does SSPG outperform the others? There is a comparison of SSPG to itself in this fashion in the two hardest environments, but that doesn't exactly cover the same area.\n* The increase in complexity over a standard policy is another weakness. SSPG adds some hyper-parameters and non-trivial implementation cost into the mix. There are also concerns about the assumptions that we have to make, such as the accuracy of the convergence criteria.\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept