Policy Gradient with Tree Expansion

## Abstract

Abstract Despite the popularity of policy gradient methods, they are known to suffer from large variance and high sample complexity.
To mitigate this, we introduce SoftTreeMax – a generalization of softmax that takes planning into account. In SoftTreeMax , we extend the traditional logits with the multi-step discounted cumulative reward, topped with the logits of future states. We consider two variants of SoftTreeMax, one for cumulative reward and one for exponentiated reward. For both, we analyze the gradient variance and reveal for the first time the role of a tree expansion policy in mitigating this variance. We prove that the resulting variance decays exponentially with the planning horizon as a function of the expansion policy. Specifically, we show that the closer the resulting state transitions are to uniform, the faster the decay. In a practical implementation, we utilize a parallelized GPU-based simulator for fast and efficient tree search. Our differentiable tree-based policy leverages all gradients at the tree leaves in each environment step instead of the traditional single-sample-based gradient. We then show in simulation how the variance of the gradient is reduced by three orders of magnitude, leading to better sample complexity compared to the standard policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in a faster run time compared to distributed PPO. Lastly, we demonstrate that high reward correlates with lower variance.

## 1 Introduction

Policy Gradient (PG; Sutton et al. ) methods for Reinforcement Learning (RL) are often the first choice for environments that allow numerous interactions at a fast pace (Schulman et al., ). Their success is attributed to several factors, including that they are easy-to-distribute to multiple workers, require no assumptions on an underlying value function, and have both on-policy and off-policy variants. Despite their popularity, PG algorithms are also notoriously unstable since they compute gradients over entire trajectories (Liu et al., ; Xu et al., ). As a result, PG algorithms tend to be highly inefficient in terms of sample complexity. Several solutions were proposed to mitigate the instability of PG methods, including baseline subtraction (Greensmith et al., ; Weaver & Tao, ; Thomas & Brunskill, ; Wu et al., ), anchor-point averaging (Papini et al., ), and other variance reduction techniques (Zhang et al., ; Shen et al., ; Pham et al., ).

A second family of algorithms that achieved state-of-the-art results in several domains is based on planning (Silver et al., ; Ye et al., ). Planning is exercised primarily in the context of value-based RL and is usually implemented using a Tree Search (TS; Coulom ; Silver ).
In this work, we
combine PG with TS by introducing a parameterized differentiable policy that incorporates tree expansion. Namely, our SoftTreeMax policy replaces the standard policy logits of a state and action, with the expected value of trajectories that originate from these state and action.

Combining TS into PG suite should be done with care given the biggest hurdle of PG – its high gradient variance. This raises prominent actionable questions that were ignored until this work: How does the tree-expansion policy affect the PG variance? And, can we design tree-expansion that is guaranteed to strongly reduces that variance?
Here, we analyze the gradient variance of SoftTreeMax, and provide a practical methodology to choose the expansion policy to minimize the resulting variance. Our main result shows that a desirable expansion policy is one that induces transitions as close to uniform as possible. More generally, we show that the gradient variance of SoftTreeMax decays at an exponential rate of $|\lambda_{2}|^{d},$ where $d$ is the tree depth and $\lambda_{2}$ is the second eigenvalue of the transition matrix induced by the tree expansion policy. This paper is the first to prove such a relation between PG variance and TS expansion policy.

Common practices for expanding the tree rely on a value estimate, using UCT (Kocsis & Szepesvári, ; Browne et al., ), or based on some prior knowledge such as human-collected trajectories (Silver et al., ). Our work raises the question of whether optimal variance reduction corresponds to the appealing regret properties of UCT.

To verify our results, we implemented a practical version of SoftTreeMax that exhaustively searches the entire tree and applies a neural network on its leaves. We test our algorithm in the Atari domain, where it is possible to span the whole tree of the (nearly) deterministic Atari environment. Hence, the gradient variance has no sampling component, and our variance calculations indeed match the empirical gradient variance. Our search mechanism uses a GPU simulator that allows multiple copies of the environment to be run in parallel (Dalton et al., ). To enable a tractable deep search, up to depth eight, we also introduce a pruning technique that limits the width of the tree. We do so by sampling only the most promising nodes at each level.

We integrate our SoftTreeMax GPU implementation into the popular PPO (Schulman et al., ) and compare it to the flat distributed variant of PPO. For a fair comparison, we also run the distributed PPO baseline with the parallel GPU emulator by Dalton et al. ().
In all tested Atari games, our results outperform the baseline and obtain up to 5x more reward. We further show in Section [6](#S6) that the associated gradient variance is smaller by three orders of magnitude in all games, demonstrating the relation between low gradient variance and high reward.

We summarize our key contributions:

- 1.
We explore the relation between two seemingly unrelated families of SoTA approaches: PG and TS, and show how they can be combined.
- 2.
We introduce SoftTreeMax: A novel parametric policy that generalizes softmax to planning. We propose both cumulative and exponentiated reward variants.
- 3.
We prove that the gradient variance of SoftTreeMax in its two variants decays exponentially with its TS depth.
Our analysis sheds new light on the choice of tree expansion policy. It raises the question of optimality in terms of variance versus the previously studied regret.
- 4.
We implement a differentiable deep version of SoftTreeMax that employs a parallelized GPU TS. We demonstrate how its gradient variance is reduced by three orders of magnitude over PPO while obtaining up to 5x reward.

## 2 Preliminaries

We follow the standard notation by (Puterman, ). Consider a discounted Markov Decision Process (MDP) $\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma)$, where $\mathcal{S}$ is a finite state space of size $S$, $A$ is a finite action space of size $A$, $r:\mathcal{S}\times\mathcal{A}\to[0,1]$ is the reward function, $P:\mathcal{S}\times\mathcal{A}\to\Delta_{\mathcal{S}}$ is the transition function, and $\gamma\in(0,1)$ is the discount factor. In vector form, denote the transition matrix starting from state $s$ by $[P_{s}]_{a,s^{\prime}}=\Pr(s^{\prime}|a,s)\in[0,1]^{A\times S},$ and the corresponding reward vector by $R_{s}=r(s,\cdot)\in\mathbb{R}^{A}$.

Let $\pi:\mathcal{S}\rightarrow\Delta_{\mathcal{A}}$ be a stationary policy. We define the induced transition matrix $P^{\pi}(s^{\prime}|s)=\sum_{a}\pi(a|s)\Pr(s^{\prime}|s,a)$ and reward function $R_{\pi}(s)=\sum_{a}\pi(a|s)r(s,a)$. Denote by $\mu_{\pi}\in\mathbb{R}^{S}$ the stationary distribution of $P^{\pi},$ s.t. $\mu_{\pi}^{\top}P^{\pi}=P^{\pi}.$ Also, let $V^{\pi}\in\mathbb{R}^{S}$ be the value function of $\pi$ defined by $V^{\pi}(s)=\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r\left(s_{t},\pi(s_{t})\right)\mid s_{0}=s\right]$, and let $Q^{\pi}\in\mathbb{R}^{S\times A}$ be the Q-function such that $Q^{\pi}(s,a)=\mathbb{E}^{\pi}\left[r(s,a)+\gamma V^{\pi}(s^{\prime})\right]$.

Our goal is to find an optimal policy $\pi^{\star}$ such that

$$ $V^{\star}(s)\equiv V^{\pi^{\star}}(s)=\max_{\pi}V^{\pi}(s),\quad\forall s\in\mathcal{S}.$ $$

Lastly, for the analysis in Section [4](#S4), we introduce the following vector notation. Denote by $\Theta\in\mathbb{R}^{S}$ the vector representation of $\theta(s)~{}\forall s\in\mathcal{S}.$ For a vector $u$, denote by $\exp(u)$ the coordinate-wise exponent of $u$ and by $D(u)$ the diagonal square matrix with $u$ in its diagonal. For matrix $A$, denote its $i$-th eigenvalue by $\lambda_{i}(A).$ Denote the $k$-dimensional identity matrix and all-ones vector by $I_{k}$ and $\textbf{1}_{k},$ respectively. We denote the trace operator by $\operatorname{Tr}.$ Finally, We treat all vectors as column vectors.

### 2.1 Policy Gradient

PG schemes seek to maximize the cumulative reward as a function of the parameterized policy $\pi_{\theta}(a|s)$ by performing gradient steps on $\theta$.
The celebrated Policy Gradient Theorem (Sutton et al., ) states that

$$ $\frac{\partial}{\partial\theta}\left(\mu_{\pi_{\theta}}^{\top}V^{\pi_{\theta}}\right)=\mathbb{E}_{s\sim{\mu_{\pi_{\theta}}},a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a)\right].$ $$

The variance of the gradient is thus

$$ $\operatorname{Var}_{s\sim{\mu_{\pi_{\theta}}},a\sim\pi_{\theta}(\cdot|s)}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a)\right).$ (1) $$

In the notation above, we denote the variance of a vector random variable $X$ by:

$$ $\operatorname{Var}_{x}\left(X\right)=\operatorname{Tr}\left[\mathbb{E}_{x}\left[\left(X-\mathbb{E}_{x}X\right)^{\top}\left(X-\mathbb{E}_{x}X\right]\right)\right],$ $$

similarly as in (Greensmith et al., ). From here on, we drop the subscript from $\operatorname{Var}$ in ([1](#S2.E1)) for brevity.

When the action space is discrete, a commonly used parameterized policy is softmax:

$$ $\pi_{\theta}(a|s)\propto\exp\left(\theta(s,a)\right),$ $$

where $\theta:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is a state-action parametrization.

## 3 SoftTreeMax : Exponent of trajectories

We introduce a new family of policies called SoftTreeMax, which are a model-based generalization of the popular softmax. We propose two variants: Cumulative (C-SoftTreeMax) and Exponentiated (E-SoftTreeMax). In both variants, we replace the generic softmax logits $\theta(s,a)$ with the score of a trajectory of horizon $d$ starting from $s,a,$ generated by applying a behavior policy $\pi_{b}$. In C-SoftTreeMax, we exponentiate the expectation of the logits. In E-SoftTreeMax, we first exponentiate the logits, and only then compute their expectation.

Logits. Let the SoftTreeMax logit $\ell_{s,a}(d;\theta)$ be a random variable depicting the score of a trajectory of horizon $d$ starting from $s,a$ and following the policy $\pi_{b}$ :

$$ $\ell_{s,a}(d;\theta)=\sum_{t=0}^{d-1}\gamma^{t}r_{t}+\gamma^{d}\theta(s_{d}).$ (2) $$

Namely, $s_{0}=s,~{}a_{0}=a,~{}a_{t}\sim\pi_{b}(\cdot|s_{t})~{}\forall t\geq 1,$ and $r_{t}\equiv r\left(s_{t},a_{t}\right).$
For brevity of the analysis, we let the parametric score $\theta$ in ([2](#S3.E2)) be state-based, similarly to a value function. Instead, one could use a state-action input analogous to a Q-function. This freedom allows easy integration of SoftTreeMax to the two types of RL algorithm implementations in standard packages.

C-SoftTreeMax. Given an inverse temperature parameter $\beta$, let C-SoftTreeMax be

$$ $\pi_{d,\theta}^{\text{C}}(a|s)\propto\exp\left[\beta\mathbb{E}^{\pi_{b}}\ell_{s,a}(d;\theta)\right].$ (3) $$

C-SoftTreeMax gives higher weight for actions that result in higher expected returns. While standard softmax relies entirely on parametrization $\theta,$ C-SoftTreeMax also interpolates a Monte-Carlo portion of the reward.

Using the monotone convergence theorem (since rewards are non-negative), it follows that when $d\rightarrow\infty,$

$$ $\pi_{d\rightarrow\infty,\theta}^{\text{C}}(a|s)\propto\exp\left[\beta Q^{\pi_{b}}(s,a)\right],$ $$

corresponding to Boltzmann exploration (Sutton et al., ) using the behavior policy $\pi_{b}$.

E-SoftTreeMax. A second natural operator to consider is E-SoftTreeMax, in which the expectation is taken outside the exponent:

$$ $\pi_{d,\theta}^{\text{E}}(a|s)\propto\mathbb{E}^{\pi_{b}}\exp\left[\left(\beta\ell_{s,a}(d;\theta)\right)\right].$ (4) $$

This objective corresponds to the exponentiated reward objective which is often used for risk-sensitive RL (Howard & Matheson, ; Fei et al., ; Noorani & Baras, ). The common risk-sensitive objective is of the form $\log\mathbb{E}[\exp(\delta R)],$ where $\delta$ is the risk parameter and $R$ is the cumulative reward. Similarly to that literature, the exponent in ([4](#S3.E4)) emphasizes the most promising trajectories.

SoftTreeMax properties. SoftTreeMax is a natural model-based generalization of softmax. For $d=0$, both variants above coincide, since ([2](#S3.E2)) becomes deterministic. In that case and for a state-action parametrization, they reduce to standard softmax.
When $\beta\rightarrow 0$, both variants again coincide and sample actions uniformly (exploration). When $\beta\rightarrow\infty,$ the policies become deterministic and greedily optimize for the best trajectory (exploitation). The best trajectory is in expectation in the case of C-SoftTreeMax, and in terms of best sample-path for E-SoftTreeMax.

SoftTreeMax convergence. Under regularity conditions, for any parametric policy, PG converges to local optima (Bhatnagar et al., ), and thus also SoftTreeMax. Specifically for softmax PG, asymptotic (Agarwal et al., ) and rate results (Mei et al., ) were recently obtained. A future direction would be to extend those for the convergence properties of SoftTreeMax.

SoftTreeMax gradient.
The two variants of SoftTreeMax involve an expectation. This expectation is taken over $S^{d}$ many trajectories from the root state $s$ and are weighted according to their probability. Thus, during the PG training process, the gradient $\nabla_{\theta}\log\pi_{\theta}$ is calculated using a weighted sum of gradients over all reachable states starting from $s$.
Our method exploits the exponential number of trajectories to reduce the variance.
Indeed,
in the next section we prove that the gradient variance of SoftTreeMax decays exponentially fast as a function of the behavior policy $\pi_{b}$ and trajectory length $d$. In the experiments in Section [6](#S6), we also show how the practical version of SoftTreeMax achieves a significant reduction in the noise of the PG process and leads to faster convergence and higher reward.

## 4 Theoretical Analysis

In this section, we bound the variance of PG when using SoftTreeMax policy. Specifically, we show that the variance decreases exponentially with the tree depth, where the rate is determined by the second eigenvalue of the transition kernel induced by $\pi_{b}.$ We analyze the gradient variance w.r.t. state-action frequencies, as a function of problem parameters. Other types of analyses could have instead focused on the estimation aspect in the context of sampling. Indeed, in our implementation in Section [5](#S5), we manage to avoid sampling and directly compute the expectations in Eqs. ([3](#S3.E3)) and ([4](#S3.E4)). As we show later, we do so by leveraging efficient parallel simulation on the GPU in feasible run-time. In our application, due to the nature of the finite action space and quasi-deterministic Atari dynamics (Bellemare et al., ), our expectation estimator is noiseless. We encourage future work to account for the finite-sample variance component.

We begin with a general variance bound that holds for any parametric policy. We defer all the proofs in this section to Appendix [A.1](#A1.SS1).

###### Lemma 4.1 (Bound on the policy gradient variance) .

For any parametric policy $\pi_{\theta}$ and function $Q^{\pi_{\theta}}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},$

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q^{\pi_{\theta}}(s,a)\right)$ $\displaystyle\quad\quad\leq\max_{s,a}\left[Q^{\pi_{\theta}}(s,a)\right]^{2}\max_{s}||\nabla_{\theta}\log\pi_{\theta}(\cdot|s)||_{F}^{2},$ $$

where $\nabla_{\theta}\log\pi_{\theta}(\cdot|s)\in\mathbb{R}^{A\times\dim(\theta)}$ is a matrix whose $a$-th row is $\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}$.

Hence, to bound ([1](#S2.E1)), it is sufficient to bound the Frobenius norm of the policy gradient $\nabla_{\theta}\log\pi_{\theta}(\cdot|s)$ for any $s$.

A common assumption in the RL literature (Szepesvári, ) that we adopt for the remainder of the section is that the transition matrix $P^{\pi_{b}},$ induced by the behavior policy $\pi_{b},$ is irreducible and aperiodic. Subsequently, its second highest eigenvalue holds: $|\lambda_{2}(P^{\pi_{b}})|<1$.

From here on, we split the variance results for the two variants of SoftTreeMax to two subsections. For C-SoftTreeMax, the analysis is simpler and we provide an exact bound. The case of E-SoftTreeMax is more involved and we provide for it a more general result. In both cases, we show that the variance decays exponentially with the planning horizon.

###### Lemma 4.1 (Bound on the policy gradient variance) .

### 4.1 Variance of C- SoftTreeMax

We express C-SoftTreeMax in vector form as follows.

###### Lemma 4.2 (Vector form of C- SoftTreeMax ) .

For $d\geq 1,$ ([3](#S3.E3)) is given by

$$ $\pi_{d,\theta}^{\text{C}}(\cdot|s)=\frac{\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]}{\textbf{1}_{A}^{\top}\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]},$ (5) $$

where

$$ $C_{s,d}=R_{s}+P_{s}\left[\sum_{h=1}^{d-1}\gamma^{h}\left(P^{\pi_{b}}\right)^{h-1}\right]R_{\pi_{b}}.$ (6) $$

The matrix $C_{s,d}\in\mathbb{R}^{A\times S}$ represents the cumulative discounted reward in expectation along the trajectory of horizon $d.$ Starting from the state $s,$ the reward $R_{s}$ is collected and a transition occurs according to $P_{s}$. Then, the policy $\pi_{b}$ is applied to obtain the reward $R_{\pi_{b}}$ and transition, and the process repeats. When depth $d$ is reached, we apply the score function on the last state as depicted in ([5](#S4.E5)).

Next, we express the policy gradient of C-SoftTreeMax

###### Lemma 4.3 (Gradient of C- SoftTreeMax ) .

The C-SoftTreeMax gradient of dimension $A\times S$ is given by

$$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}=\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}{(\pi_{d,\theta}^{\text{C}}})^{\top}\right]P_{s}\left(P^{\pi_{b}}\right)^{d-1},$ $$

where for brevity, we drop the $s$ index in the policy above, i.e., ${\pi_{d,\theta}^{\text{C}}\equiv\pi_{d,\theta}^{\text{C}}(\cdot|s).}$

We are now ready to present our first main result:

###### Theorem 4.4 (Exponential variance decay of C- SoftTreeMax ) .

For every $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},$ the C-SoftTreeMax policy gradient is bounded by

$$ $\displaystyle\operatorname{Var}$ $\displaystyle\left(\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}(a|s)Q(s,a)\right)$ $\displaystyle\quad\quad\quad\leq 2\frac{A^{2}S^{2}\beta^{2}}{(1-\gamma)^{2}}\gamma^{2d}|\lambda_{2}(P^{\pi_{b}})|^{2(d-1)}.$ $$

Although we provide a rigorous proof in Appendix [A.1.4](#A1.SS1.SSS4), since the proof relatively accessible, we briefly outline its essence here.

###### Proof outline.

Lemma [4.1](#S4.Thmtheorem1) allows us to bound the variance using a direct bound on the gradient norm.
The gradient is given in Lemma [4.3](#S4.Thmtheorem3) as a product of three matrices, which we now study from right to left. The matrix $P^{\pi_{b}}$ is a row-stochastic matrix. Because the associated Markov chain is irreducible and aperiodic, it has a unique stationary distribution. This implies that $P^{\pi_{b}}$ has one and only one eigenvalue equal to $1;$ all others have magnitude strictly less than $1.$ Let us suppose that all these other eigenvalues have multiplicity $1$ (the general case with repeated eigenvalues can be handled via Jordan decompositions as in (Pelletier, , Lemma1)). Then, $P^{\pi_{b}}$ has the spectral decomposition

$$ $P^{\pi_{b}}=\textbf{1}_{S}\mu^{\top}_{\pi_{b}}+\sum_{i=2}^{S}\lambda_{i}v_{i}u_{i}^{\top},$ $$

where $\lambda_{i}$ is the $i$-th eigenvalue of $P^{\pi_{b}}$ (ordered in descending order according to their magnitude) and $u_{i}$ and $v_{i}$ are the corresponding left and right eigenvectors, respectively.
Therefore,

$$ $(P^{\pi_{b}})^{d-1}=\textbf{1}_{S}\mu^{\top}_{\pi_{b}}+\sum_{i=2}^{S}\lambda_{i}^{d-1}v_{i}u_{i}^{\top}.$ (7) $$

The second matrix in the gradient relation in Lemma [4.3](#S4.Thmtheorem3), $P_{s},$ is a rectangular transition matrix that translates the vector of all ones from dimension $S$ to $A:$ $P_{s}\textbf{1}_{S}=\textbf{1}_{A}.$

Lastly, the first matrix $\left[I_{A}-\textbf{1}_{A}{(\pi_{d,\theta}^{\text{C}}})^{\top}\right]$
is a projection whose null-space includes
the vector $\textbf{1}_{A},$ i.e., $\left[I_{A}-\textbf{1}_{A}{(\pi_{d,\theta}^{\text{C}}})^{\top}\right]\textbf{1}_{A}=0.$

Combining the three properties above when multiplying the three matrices of the gradient, it is easy to see that the first term in ([7](#S4.E7)) gets canceled, and we are left with bounded summands scaled by $\lambda_{i}(P^{\pi_{b}})^{d-1}.$ Recalling that $|\lambda_{i}(P^{\pi_{b}})|<1$ and that $|\lambda_{2}|>|\lambda_{3}|>\dots$ for $i=2,\dots,S,$ we obtain the desired result.
∎

Theorem [4.4](#S4.Thmtheorem4) guarantees that the variance of the gradient decays exponentially with $d,$ regardless of $\gamma.$ It also provides a novel insight that drives us to choose the behavior policy $\pi_{b}$ as the policy that minimizes the absolute second eigenvalue of the $P^{\pi_{b}}.$ Indeed, the second eigenvalue of a Markov chain has known connections to its connectivity and its rate of convergence to the stationary distribution (Levin & Peres, ).

Optimal variance decay. To achieve the best reduction in variance, the behavior policy $\pi_{b}$ should be chosen to achieve uniformity. That is, that transitions induced by the interaction of $\pi_{b}$ with the environment are uniform. In that case, $P^{\pi_{b}}$ is a rank one matrix of the form $\textbf{1}_{S}\mu_{\pi_{b}}^{\top},$ and $\lambda_{2}(P^{\pi_{b}})=0.$ Then, $\operatorname{Var}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)\right)=0.$ As we show in Section [5](#S5), we choose our tree expansion policy accordingly.

Figure: Figure 1: A comparison of the analytical PG variance and our bound for E-SoftTreeMax on randomly drawn MDPs. We present three cases for $P^{\pi_{b}}:$ (i) close to uniform, (ii) drawn randomly, and (iii) close to a permutation matrix. This experiment verifies the optimal and worse-case rate decay cases. The variance bounds here are taken from Theorem [4.7](#S4.Thmtheorem7) where we substitute $\alpha=|\lambda_{2}(P^{\pi_{b}})|.$
Refer to caption: /html/2301.13236/assets/x1.png

Worst-case variance decay. In contrast, and somewhat surprisingly, when $\pi_{b}$ is chosen so that the dynamics is deterministic, there is no guarantee that it will decay exponentially fast. For example, if $P^{\pi_{b}}$ is a permutation matrix, then $\lambda_{2}(P^{\pi_{b}})=1,$ and advancing the tree amounts to only updating the gradient of one state for every action, as in the basic softmax.

###### Lemma 4.2 (Vector form of C- SoftTreeMax ) .

###### Lemma 4.3 (Gradient of C- SoftTreeMax ) .

###### Theorem 4.4 (Exponential variance decay of C- SoftTreeMax ) .

###### Proof outline.

### 4.2 Variance of E- SoftTreeMax

The proof of the variance bound for E-SoftTreeMax is similar to that of C-SoftTreeMax, but more involved. It also requires the assumption that the reward depends only on the state, i.e. $r(s,a)\equiv r(s).$ This is indeed the case in most standard RL environments such as Atari and Mujoco.

We begin with expressing E-SoftTreeMax in vector form.

###### Lemma 4.5 (Vector form of E- SoftTreeMax ) .

For $d\geq 1$, ([4](#S3.E4)) is given by

$$ $\pi_{d,\theta}^{\text{E}}(\cdot|s)=\frac{E_{s,d}\exp(\beta\gamma^{d}\Theta)}{1_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)},$ (8) $$

where

$$ $E_{s,d}=P_{s}\prod_{h=1}^{d-1}\left(D\left(\exp(\beta\gamma^{h}R)\right)P^{\pi_{b}}\right).$ (9) $$

The vector $R$ above is the $S$-dimensional vector whose $s$-th coordinate is $r(s).$

The matrix $E_{s,d}\in\mathbb{R}^{A\times S}$ has a similar role to $C_{s,d}$ from ([6](#S4.E6)), but it represents the exponentiated cumulative discounted reward. Accordingly, it is a product of $d$ matrices as opposed to a sum. It captures the expected reward sequence starting from $s$ and then iteratively following $P^{\pi_{b}}.$ After $d$ steps, we apply the score function on the last state as in ([8](#S4.E8)).

###### Lemma 4.6 (Gradient of E- SoftTreeMax ) .

The E-SoftTreeMax gradient of dimension $A\times S$ is given by

$$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}=$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}E_{s,d}D(\exp(\beta\gamma^{d}\Theta))}{{\bf{1}}^{\top}_{A}E_{s,d}\exp(\beta\gamma^{d}\Theta)},$ $$

where for brevity, we drop the $s$ index in the policy above, i.e., ${\pi_{d,\theta}^{\text{E}}\equiv\pi_{d,\theta}^{\text{E}}(\cdot|s).}$

This gradient structure is harder to handle than that of C-SoftTreeMax in Lemma [4.3](#S4.Thmtheorem3), but here we also prove an exponential variance decay nonetheless.

###### Theorem 4.7 (Exponential variance decay of E- SoftTreeMax ) .

There exists $\alpha\in\left(0,1\right)$ such that, for any function $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},$

$$ $\operatorname{Var}\left(\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}(a|s)Q(s,a)\right)\in\mathcal{O}\left(\beta^{2}\gamma^{2d}\alpha^{2d}\right).$ $$

If all rewards are equal ($r\equiv\text{const}$), then $\alpha=|\lambda_{2}(P^{\pi_{b}})|$.

The proof structure is similar in spirit to that of Theorem [4.4](#S4.Thmtheorem4), but several new technical arguments are needed. We give it in full in Appendix [A.1.4](#A1.SS1.SSS4), but briefly outline it here.

###### Proof outline.

Recall that thanks to Lemma [4.1](#S4.Thmtheorem1), we can bound the PG variance using a direct bound on the gradient norm. The definition of the induced norm is

$$ $\|\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}\|=\max_{z:\|z\|=1}\|\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}z\|,$ $$

with $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}$ given in Lemma [4.6](#S4.Thmtheorem6).
Let $z\in\mathbb{R}^{S}$ be an arbitrary vector such that $\|z\|=1$. Then,
$z=\sum_{i=1}^{S}c_{i}z_{i},$
where $c_{i}$ are scalar coefficients and $z_{i}$ are vectors spanning the $S$-dimensional space. In the full proof, we show our specific choice of $z_{i}$ and prove they are linearly independent given that choice. We do note that $z_{1}=\textbf{1}_{S}.$

The first part of the proof relies on the fact that $(\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}})z_{1}=0.$ This is easy to verify using Lemma [4.6](#S4.Thmtheorem6) together with ([8](#S4.E8)), and because $\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]$ is a projection matrix whose null-space is spanned by $\textbf{1}_{S}.$ Thus,

$$ $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}z=\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}\sum_{i=2}^{S}c_{i}z_{i}.$ $$

In the second part of the proof, we focus on $E_{s,d}$ from ([9](#S4.E9)), which appears within $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}.$ Notice that $E_{s,d}$ consists of the product
$\prod_{h=1}^{d-1}\left(D\left(\exp(\beta\gamma^{h}R\right)P^{\pi_{b}}\right).$
Even though the elements in this product are not stochastic matrices, in the full proof we show how to normalize each of them to a stochastic matrix $B_{h}.$ We thus obtain that

$$ $E_{s,d}=P_{s}D(M_{1})\prod_{h=1}^{d-1}B_{h},$ $$

where $M_{1}\in\mathbb{R}^{S}$ is some strictly positive vector. Then, we can apply a result by Mathkar & Borkar (), which itself builds on (Chatterjee & Seneta, ). The result states that the product of stochastic matrices $\prod_{h=1}^{d-1}B_{h}$ of our particular form converges exponentially fast to a matrix of the form $\textbf{1}_{S}\mu^{\top}$ s.t. $\|\textbf{1}_{S}\mu^{\top}-\prod_{h=1}^{d-1}B_{h}\|\leq C\alpha^{d}$ for some constant $C.$

Figure: Figure 2: SoftTreeMax policy. Our exhaustive parallel TS expands all actions at each state up to depth $d$ ($=2$ here). The leaf state of every trajectory is used as input to the policy network. The output is then added to the trajectory’s cumulative reward as described in ([2](#S3.E2)). I.e., instead of the standard softmax logits, we add the cumulative discounted reward to the policy network output. This policy is differentiable and can be easily integrated into any PG algorithm. In this work, we build on PPO and use its loss function to train the policy network.
Refer to caption: /html/2301.13236/assets/x2.png

Lastly, $\textbf{1}_{S}\mu_{\pi_{b}}^{\top}$ gets canceled due to our choice of $z_{i},~{}i=2,\dots,S.$ This observation along with the above fact that the remainder decays then shows that $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}\sum_{i=2}^{S}z_{i}=\mathcal{O}(\alpha^{d}),$ which gives the desired result.
∎

Although our proof guarantees that $\alpha=|\lambda_{2}(P^{\pi_{b}})|$ only in the constant-reward case, we conjecture that this is also true in the general case. To demonstrate this, we run the following simulation. We drew a random finite MDP, parameter vector $\Theta\in\mathbb{R}^{S}_{+},$ and behavior policy $\pi_{b}.$ We then analytically computed the PG variance of E-SoftTreeMax as given in ([1](#S2.E1)) and compared it to $|\lambda_{2}(P^{\pi_{b}})|^{d}.$ As seen, the true variance and our bound matched almost identically. This suggests that indeed $\alpha=|\lambda_{2}(P^{\pi_{b}})|.$ We repeat this experiment three times for different $P^{\pi_{b}}:$ (i) close to uniform, (ii) drawn randomly, and (iii) close to a permutation matrix. The three cases match our takeaways on the optimal and worst-case rate decay cases. We ran multiple such experiments and in all of them the lines match closely; we give here one such instance. To account the for constants, we match the values for the first point in $d=1.$

###### Lemma 4.5 (Vector form of E- SoftTreeMax ) .

###### Lemma 4.6 (Gradient of E- SoftTreeMax ) .

###### Theorem 4.7 (Exponential variance decay of E- SoftTreeMax ) .

###### Proof outline.

## 5 SoftTreeMax : Deep Parallel Implementation

Following the success of deep RL (Mnih et al., ), deep neural networks are used nowadays almost exclusively in practice. Depending on the RL algorithm, a loss function is defined and gradients on the network weights can be calculated.
In PG methods, the scoring function used in the softmax is commonly replaced by a neural network $W_{\theta}$:

$$ $\pi_{\theta}(a|s)\propto\exp\left(W_{\theta}(s,a)\right).$ $$

Similarly, we implement SoftTreeMax by replacing $\theta(s)$ in ([2](#S3.E2)) with a neural network $W_{\theta}(s)$. Although both variants of SoftTreeMax from Section [3](#S3) involve computing an expectation, this can be hard in general. One approach to handle it is with sampling, though these introduce estimation variance into the process. We leave the question of sample-based theory and algorithmic implementations for future work.

Instead, in finite action space environments such as Atari, we compute the exact expectation in SoftTreeMax with an exhaustive TS of depth $d$. Despite the exponential computational cost of spanning the entire tree, recent advancements in parallel GPU-based simulation allow efficient expansion of all nodes at the same depth simultaneously (Dalal et al., ; Rosenberg et al., ). This is possible when a simulator is implemented on GPU (Dalton et al., ; Makoviychuk et al., ; Freeman et al., ), or when a forward model is learned (Kim et al., ; Ha & Schmidhuber, ). To reduce the complexity to be linear in depth, we apply tree pruning to a limited width in all levels. We do so by sampling only the most promising actions at each level.

To summarize, in the practical SoftTreeMax algorithm we perform an exhaustive TS to obtain all trajectories up to depth $d.$ We expand the tree by exhaustively expanding all actions, which corresponds to a uniform tree expansion policy $\pi_{b}.$ We apply a neural network on the leaf states, and accumulate the result with the rewards along each trajectory to obtain the logits in ([2](#S3.E2)). Finally, we aggregate the results using C-SoftTreeMax. We leave experiments E-SoftTreeMax for future work on risk-averse RL. During training, the gradient propagates to the NN weights of $W_{\theta}.$ When the gradient $\nabla_{\theta}\log\pi_{d,\theta}$ is calculated at each time step, it updates $W_{\theta}$ for all leaf states, similarly to Siamese networks (Bertinetto et al., ). An illustration of the policy is given in Figure [2](#S4.F2).

## 6 Experiments

We conduct our experiments on multiple games from the Atari simulation suite (Bellemare et al., ). As a baseline, we train a PPO (Schulman et al., ) agent with $256$ workers in parallel. In a hyperparameter search, we found this number of workers to be the best in terms of run-time. The environment engine is the highly efficient Atari-CuLE (Dalton et al., ), a CUDA-based version of Atari that runs on GPU. Similarly, we use Atari-CuLE for the GPU-based breadth-first TS as done in (Dalal et al., ).
We then train SoftTreeMax for depths $d=1\dots 8,$ with a single worker. We use five seeds for each experiment.

For the implementation, we extend Stable-Baselines3 (Raffin et al., ) with all parameters taken as default from the original PPO paper (Schulman et al., ). We will release the code upon publication. For depths $d\geq 3$, we limited the tree to a maximum width of $1024$ nodes and pruned non-promising trajectories in terms of estimated weights. Since the distributed PPO baseline advances significantly faster in terms of environment steps, for a fair comparison, we ran all experiments for one week on the same machine and use the wall-clock time as the x-axis. We use Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz equipped with one NVIDIA Tesla V100 32GB.

In Figure [3](#S6.F3), we plot the reward and variance of SoftTreeMax for each game, as a function of depth. The dashed lines are the results for PPO. Each value is taken after convergence, i.e., the average over the last $20\%$ of the run. The numbers represent the average over five seeds per game. We choose to exclude the standard deviation to avoid excessive clutter in the plot. The plot conveys three intriguing conclusions. First, in all cases, SoftTreeMax achieves significantly higher reward than PPO. Its gradient variance is also orders of magnitude lower than that of PPO. Second, the reward and variance are negatively correlated – they mirror each other in almost all of the games. This phenomenon demonstrates how crucial it is to lower the variance of PG for improving performance. And specifically, it highlights the benefits of SoftTreeMax over “flat” PG. The third conclusion is that each game has a different sweet-spot in terms of optimal TS depth. Recall that we limit the run-time in all experiments to one week. The deeper the TS, the slower each step and less steps are finished by the end of the run. This type of comparison also explains why there is no reason to expect monotone variance reduction as a function of depth.

Figure: Figure 3: Reward and Gradient variance: GPU SoftTreeMax (single worker) vs PPO ($\bf{256}$ GPU workers). The blue reward plots show the average of $50$ evaluation episodes. The red variance plots show the average gradient variance of the corresponding training runs, averaged over five seeds. The dashed lines represent the same for PPO. Note theat the variance y-axis is in log-scale. The reward and variance are negatively correlated and mirror each other in almost all games. This demonstrates the necessity to lower the variance of PG for improving performance. We limit the training run-time in all experiments to one week. The deeper the TS, the slower each step and less steps are finished by the end of the training run. This explains the non-monotone performance and variance as a function of depth.
Refer to caption: /html/2301.13236/assets/figures/grad_var_leg2.png

We also provide the training curves in Figure [4](#S6.F4). For brevity, we exclude a few of the depths from the plots. As seen, there is a clear benefit for SoftTreeMax over distributed PPO with the standard softmax policy. In most games, PPO with the SoftTreeMax policy shows very high sample efficiency: it achieves higher episodic reward even though it observes much less episodes, for the same running time.

Figure: Figure 4: Training curves: GPU SoftTreeMax (single worker) vs PPO ($\bf{256}$ GPU workers). The plots show average reward and standard deviation over five seeds. The x-axis is the wall-clock time. The runs ended after a maximum of 200M time-steps, and after no longer than one week. The standard PPO finished in less than one week. The training curves correspond to the evaluation runs in Figure [3](#S6.F3).
Refer to caption: /html/2301.13236/assets/figures/pg-convergence_legend.png

## 7 Related Work

Our work intersects several fields of the RL literature:

Softmax Operator.
The softmax policy became a canonical part of PG to the point where theoretical results of PG focus specifically on it (Zhang et al., ; Mei et al., ; Li et al., ; Schulman et al., ; Haarnoja et al., ). Even though we focus on a tree extension to the softmax policy, the methodology we propose is general and can be easily applied to other discrete or continuous parameterized policies as in (Mei et al., ; Miahi et al., ).

Tree Search.
Planning with a TS is the process of using a forward model to consider possible future trajectories and decide on the best action at the root. One famous such algorithm is Monte-Carlo TS (MCTS; Browne et al. ) used in AlphaGo (Silver et al., ) and MuZero (Schrittwieser et al., ). Other principal algorithms such as Value Iteration, Policy Iteration and DQN were also shown to give an improved performance with a tree search extensions (Efroni et al., ; Dalal et al., ).

Risk Aversion.
Many works considered an exponential utility function for risk aversion (Chen et al., ; Garcıa & Fernández, ; Fei et al., ). This utility function is the same as E-SoftTreeMax formulation from ([4](#S3.E4)), but we have it directly in the policy instead of the objective.

Reward-free RL.
We showed that the gradient variance is minimized when the transitions induced by the behavior policy $\pi_{b}$ are uniform. This is expressed by the second eigenvalue of the transition matrix $P^{\pi_{b}}$. This notion of uniform exploration is common to the reward-free RL setup (Jin et al., ). Several such works considered the same second eigenvalue in their analysis (Liu & Brunskill, ; Tarbouriech & Lazaric, ).

## 8 Discussion

Planning in RL is typically carried out with value-based algorithms due to its seamless integration with the Bellman operator, leaving aside the popular class of PG methods. In this work, we introduced for the first time a differentiable parametric policy that combines TS with PG. We prove that SoftTreeMax is essentially an exponential variance reduction technique and provide novel insight on how to choose the expansion policy to minimize the gradient variance. It is an open question whether optimal variance reduction corresponds to the appealing regret properties tackled by UCT (Kocsis & Szepesvári, ).

Mitigating the known sample inefficiency issue, SoftTreeMax achieves better performance than the widely used PPO with multiple workers and softmax policy. Our method can be further applied to continuous control tasks, or in tasks where the forward model is learned with some estimation error. Other possible future directions are: (i) to study the implications of sampling trajectories instead of directly calculating their expectation; (ii) analyze the convergence rate of SoftTreeMax, and (iii) to extend SoftTreeMax to adaptively changing depths to optimize run-time and performance.

## Appendix A Appendix

### A.1 Proofs

#### A.1.1 Proof of Lemma 4.1 – Bound on the policy gradient variance

For any parametric policy $\pi_{\theta}$ and function $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},$

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)\right)\leq\max_{s,a}\left[Q(s,a)\right]^{2}\max_{s}||\nabla_{\theta}\log\pi_{\theta}(\cdot|s)||_{F}^{2},$ $$

where $\nabla_{\theta}\log\pi_{\theta}(\cdot|s)\in\mathbb{R}^{A\times\dim(\theta)}$ is a matrix whose $a$-th row is $\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}$.

###### Proof.

The variance for a parametric policy $\pi_{\theta}$ is given as follows:

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q(a,s)\right)=$ $\displaystyle\mathbb{E}_{s\sim\mu_{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)^{2}\right]-$ $\displaystyle\quad\mathbb{E}_{s\sim\rho_{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)\right]^{\top}\mathbb{E}_{s\sim\mu_{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)\right],$ $$

where $Q(s,a)$ is the currently estimated Q-function and $\mu_{\pi_{\theta}}$ is the stationary distribution induced by following the policy $\pi_{\theta}$. Since the second term we subtract is always positive (it is of quadratic form $v^{\top}v$) we can bound the variance by the first term:

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{\theta}(a|s)Q(a,s)\right)\leq$ $\displaystyle\mathbb{E}_{s\sim\mu_{\pi_{\theta}},a\sim\pi_{\theta}(\cdot|s)}\left[\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)^{2}\right]$ $\displaystyle=$ $\displaystyle\sum_{s}\mu_{\pi_{\theta}}(s)\sum_{a}\pi_{\theta}(a|s)\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s)Q(s,a)^{2}$ $\displaystyle\leq$ $\displaystyle\max_{s,a}\left[\left[Q(s,a)\right]^{2}\pi_{\theta}(a|s)\right]\sum_{s}\mu_{\pi_{\theta}}(s)\sum_{a}\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s)$ $\displaystyle\leq$ $\displaystyle\max_{s,a}\left[Q(s,a)\right]^{2}\max_{s}\sum_{a}\nabla_{\theta}\log\pi_{\theta}(a|s)^{\top}\nabla_{\theta}\log\pi_{\theta}(a|s)$ $\displaystyle=$ $\displaystyle\max_{s,a}\left[Q(s,a)\right]^{2}\max_{s}||\nabla_{\theta}\log\pi_{\theta}(\cdot|s)||_{F}^{2}.$ $$

∎

###### Proof.

#### A.1.2 Proof of Lemma 4.2 – Vector form of C- SoftTreeMax

In vector form, ([3](#S3.E3)) is given by

$$ $\pi_{d,\theta}^{\text{C}}(\cdot|s)=\frac{\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]}{\textbf{1}_{A}^{\top}\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]},$ (10) $$

where

$$ $C_{s,d}=R_{s}+P_{s}\left[\sum_{h=1}^{d-1}\gamma^{h}\left(P^{\pi_{b}}\right)^{h-1}\right]R_{\pi_{b}}.$ (11) $$

###### Proof.

Consider the vector $\ell_{s,\cdot}\in\mathbb{R}^{|\mathcal{A}|}.$ Its expectation satisfies

$$ $\displaystyle\mathbb{E}^{\pi_{b}}\ell_{s,\cdot}(d;\theta)$ $\displaystyle=\mathbb{E}^{\pi_{b}}\left[\sum_{t=0}^{d-1}\gamma^{t}r_{t}+\gamma^{d}\theta(s_{d})\right]$ $\displaystyle=R_{s}+\sum_{t=1}^{d-1}\gamma^{t}P_{s}(P^{\pi_{b}})^{t-1}R_{\pi_{b}}+\gamma^{d}P_{s}(P^{\pi_{b}})^{d-1}\Theta.$ $$

As required.
∎

###### Proof.

#### A.1.3 Proof of Lemma 4.3 – Gradient of C- SoftTreeMax

The C-SoftTreeMax gradient of dimension $A\times S$ is given by

$$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}=\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}{(\pi_{d,\theta}^{\text{C}}})^{\top}\right]P_{s}\left(P^{\pi_{b}}\right)^{d-1},$ $$

where for brevity, we drop the $s$ index in the policy above, i.e., ${\pi_{d,\theta}^{\text{C}}\equiv\pi_{d,\theta}^{\text{C}}(\cdot|s).}$

###### Proof.

The $(j,k)$-th entry of $\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}$ satisifes

$$ $\displaystyle[\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}]_{j,k}$ $\displaystyle=\frac{\partial\log(\pi_{d,\theta}^{\text{C}}(a^{j}|s))}{\partial\theta(s^{k})}$ $\displaystyle=\beta\gamma^{d}[P_{s}(P^{\pi_{b}})^{d-1}]_{j,k}-\frac{\sum_{a}\left[\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]\right]_{a}\beta\gamma^{d}\left[P_{s}(P^{\pi_{b}})^{d-1}\right]_{a,k}}{\textbf{1}_{A}^{\top}\exp\left[\beta\left(C_{s,d}+\gamma^{d}P_{s}\left(P^{\pi_{b}}\right)^{d-1}\Theta\right)\right]}$ $\displaystyle=\beta\gamma^{d}[P_{s}(P^{\pi_{b}})^{d-1}]_{j,k}-\beta\gamma^{d}\sum_{a}\pi_{d,\theta}^{\text{C}}(a|s)\left[P_{s}(P^{\pi_{b}})^{d-1}\right]_{a,k}$ $\displaystyle=\beta\gamma^{d}[P_{s}(P^{\pi_{b}})^{d-1}]_{j,k}-\beta\gamma^{d}\left[(\pi_{d,\theta}^{\text{C}})^{\top}P_{s}(P^{\pi_{b}})^{d-1}\right]_{k}$ $\displaystyle=\beta\gamma^{d}[P_{s}(P^{\pi_{b}})^{d-1}]_{j,k}-\beta\gamma^{d}\left[\textbf{1}_{A}(\pi_{d,\theta}^{\text{C}})^{\top}P_{s}(P^{\pi_{b}})^{d-1}\right]_{j,k}.$ $$

Now, moving back to matrix form, we obtain the lemma.
∎

###### Proof.

#### A.1.4 Proof of Theorem 4.4 – Exponential variance decay of C- SoftTreeMax

The C-SoftTreeMax policy gradient is bounded by

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}(a|s)Q(s,a)\right)\leq 2\frac{A^{2}S^{2}\beta^{2}}{(1-\gamma)^{2}}\gamma^{2d}|\lambda_{2}(P^{\pi_{b}})|^{2(d-1)}.$ $$

###### Proof.

We use Lemma [4.1](#S4.Thmtheorem1) directly. First of all, it is know that when the reward is bounded in $[0,1]$, the maximal value of the Q-function is $\frac{1}{1-\gamma}$ as the sum as infinite discounted rewards. Next, we bound the Frobenius norm of the term achieved in Lemma [4.3](#S4.Thmtheorem3), by applying the eigen-decomposition on $P^{\pi_{b}}$:

$$ $P^{\pi_{b}}=\textbf{1}_{S}\mu^{\top}+\sum_{i=2}^{S}\lambda_{i}u_{i}v_{i}^{\top},$ (12) $$

where $\mu$ is the stationary distribution of $P^{\pi_{b}}$, and $u_{i}$ and $v_{i}$ are left and right eigenvectors correspondingly.

$$ $\displaystyle||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}||_{F}$ $\displaystyle=\beta\gamma^{d}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}\left(\textbf{1}_{S}\mu^{\top}+\sum_{i=2}^{S}\lambda^{d-1}_{i}u_{i}v_{i}^{\top}\right)||_{F}$ $\displaystyle\textit{(}P_{s}\textit{ is stochastic)}\quad$ $\displaystyle=\beta\gamma^{d}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)\left(\textbf{1}_{A}\mu^{\top}+\sum_{i=2}^{S}\lambda^{d-1}_{i}P_{s}u_{i}v_{i}^{\top}\right)||_{F}$ $\displaystyle\textit{(projection nullifies }\textbf{1}_{A}\mu^{\top}\textit{)}\quad$ $\displaystyle=\beta\gamma^{d}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)\left(\sum_{i=2}^{S}\lambda^{d-1}_{i}P_{s}u_{i}v_{i}^{\top}\right)||_{F}$ (triangle inequality) $\displaystyle\leq\beta\gamma^{d}\sum_{i=2}^{S}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)\left(\lambda^{d-1}_{i}P_{s}u_{i}v_{i}^{\top}\right)||_{F}$ (matrix norm sub-multiplicativity) $\displaystyle\leq\beta\gamma^{d}|\lambda^{d-1}_{2}|\sum_{i=2}^{S}||I_{A,A}-\textbf{1}_{A}\pi^{\top}||_{F}||P_{s}||_{F}||u_{i}v_{i}^{\top}||_{F}$ $\displaystyle=\beta\gamma^{d}|\lambda^{d-1}_{2}|(S-1)||I_{A,A}-\textbf{1}_{A}\pi^{\top}||_{F}||P_{s}||_{F}$ $$

Now we can bound the norm $||I_{A,A}-\textbf{1}_{A}\pi^{\top}||_{F}$ by direct calculation:

$$ $\displaystyle||I_{A,A}-\textbf{1}_{A}\pi^{\top}||_{F}^{2}$ $\displaystyle=\operatorname{Tr}\left[\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)^{\top}\right]$ (13) $\displaystyle=\operatorname{Tr}\left[I_{A,A}-\textbf{1}_{A}\pi^{\top}-\pi\textbf{1}_{A}^{\top}+\pi^{\top}\pi\textbf{1}_{A}\textbf{1}_{A}^{\top}\right]$ (14) $\displaystyle=A-1-1+A\pi^{\top}\pi$ (15) $\displaystyle\leq 2A$ (16) $$

And from the Cauchy-Schwartz inequality:

$$ $\displaystyle||P_{s}||_{F}^{2}$ $\displaystyle=\sum_{a}\sum_{s}\left[[P_{s}]_{a,s}\right]^{2}=\sum_{a}||[P_{s}]_{a,\cdot}||_{2}^{2}\leq\sum_{a}||[P_{s}]_{a,\cdot}||_{1}||[P_{s}]_{a,\cdot}||_{\infty}\leq A.$ $$

So:

$$ $\displaystyle\operatorname{Var}\left(\nabla_{\theta}\log\pi_{d,\theta}^{\text{C}}(a|s)Q(s,a)\right)$ $\displaystyle\leq\max_{s,a}\left[Q(s,a)\right]^{2}\max_{s}||\nabla_{\theta}\log{\pi_{d,\theta}^{\text{C}}}(\cdot|s)||_{F}^{2}$ $\displaystyle\leq\frac{1}{(1-\gamma)^{2}}||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}||^{2}_{F}$ $\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\beta^{2}\gamma^{2d}|\lambda_{2}(P^{\pi_{b}})|^{2(d-1)}S^{2}(2A^{2})$ $$

Which obtains the desired bound.
∎

###### Proof.

#### A.1.5 A lower bound on C- SoftTreeMax gradient (result not in the paper)

For completeness we also supply a lower bound on the Frobenius norm of the gradient. Note that this result does not translate to the a lower bound on the variance since we have no lower bound equivalence of Lemma [4.1](#S4.Thmtheorem1).

###### Lemma A.1 .

The Frobenius norm on the gradient of the policy is lower-bounded by:

$$ $||\nabla_{\theta}\log{\pi_{d,\theta}^{\text{C}}}(\cdot|s)||_{F}\geq C\cdot\beta\gamma^{d}|\lambda_{2}(P^{\pi_{b}})|^{(d-1)}.$ (17) $$

###### Proof.

We begin by moving to the induced $l_{2}$ norm by norm-equivalence:

$$ $||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}||_{F}\geq||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}||_{2}$ $$

Now, taking the vector $u$ to be the eigenvector of the second eigenvalue of $P^{\pi_{b}}$:

$$ $\displaystyle||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}||_{2}$ $\displaystyle\geq||\beta\gamma^{d}\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}(P^{\pi_{b}})^{d-1}u||_{2}$ $\displaystyle=\beta\gamma^{d}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}u||_{2}$ $\displaystyle=\beta\gamma^{d}|\lambda_{2}(P^{\pi_{b}})|^{(d-1)}||\left(I_{A,A}-\textbf{1}_{A}\pi^{\top}\right)P_{s}u||_{2}$ $$

Note that even though $P_{s}u$ can be 0 0, that is not the common case since we can freely change $\pi_{b}$ (and therefore the eigenvectors of $P^{\pi_{b}}$).
∎

###### Lemma A.1 .

###### Proof.

#### A.1.6 Proof of Lemma 4.5 – Vector form of E- SoftTreeMax

For $d\geq 1$, ([4](#S3.E4)) is given by

$$ $\pi_{d,\theta}^{\text{E}}(\cdot|s)=\frac{E_{s,d}\exp(\beta\gamma^{d}\Theta)}{1_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)},$ (18) $$

where

$$ $E_{s,d}=P_{s}\prod_{h=1}^{d-1}\left(D\left(\exp[\beta\gamma^{h}R]\right)P^{\pi_{b}}\right)$ (19) $$

with $R$ being the $|S|$-dimensional vector whose $s$-th coordinate is $r(s).$

###### Proof.

Recall that

$$ $\ell_{s,a}(d;\theta)=r(s)+\sum_{t=1}^{d-1}\gamma^{t}r(s_{t})+\gamma^{d}\theta(s_{d}).$ (20) $$

and, hence,

$$ $\exp[\beta\ell_{s,a}(d;\theta)]=\exp\left[\beta\left(r(s)+\sum_{t=1}^{d-1}\gamma^{t}r(s_{t})+\gamma^{d}\theta(s_{d})\right)\right].$ (21) $$

Therefore,

$$ $\displaystyle\mathbb{E}[\exp\beta\ell_{s,a}(d;\theta)]={}$ $\displaystyle\mathbb{E}\left[\exp\left[\beta\left(r(s)+\sum_{t=1}^{d-1}\gamma^{t}r(s_{t})\right)\right]\mathbb{E}\left[\exp\left[\beta\left(\gamma^{d}\theta(s_{d})\right)\right]\middle|s_{1},\ldots,s_{d-1}\right]\right]$ (22) $\displaystyle={}$ $\displaystyle\mathbb{E}\left[\exp\left[\beta\left(r(s)+\sum_{t=1}^{d-1}\gamma^{t}r(s_{t})\right)\right]P^{\pi_{b}}(\cdot|s_{d-1})\right]\exp(\beta\gamma^{d}\Theta)$ (23) $\displaystyle={}$ $\displaystyle\mathbb{E}\left[\exp\left[\beta\left(r(s)+\sum_{t=1}^{d-2}\gamma^{t}r(s_{t})\right)\right]\exp[\beta\gamma^{d-1}r(s_{d-1})]P^{\pi_{b}}(\cdot|s_{d-1})\right]\exp(\beta\gamma^{d}\Theta).$ (24) $$

By repeatedly using iterative conditioning as above, the desired result follows. Note that $\exp(\beta r(s))$ does not depend on the action and is therefore cancelled out with the denominator.
∎

###### Proof.

#### A.1.7 Proof of Lemma 4.6 – Gradient of E- SoftTreeMax

The E-SoftTreeMax gradient of dimension $A\times S$ is given by

$$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}=\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}E_{s,d}D(\exp(\beta\gamma^{d}\Theta))}{{\bf{1}}^{\top}_{A}E_{s,d}\exp(\beta\gamma^{d}\Theta)},$ $$

where for brevity, we drop the $s$ index in the policy above, i.e., ${\pi_{d,\theta}^{\text{E}}\equiv\pi_{d,\theta}^{\text{E}}(\cdot|s).}$

###### Proof.

The $(j,k)$-th entry of $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}$ satisfies

$$ $\displaystyle[\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}]_{j,k}={}$ $\displaystyle\frac{\partial\log(\pi_{d,\theta}^{\text{E}}(a^{j}|s))}{\partial\theta(s^{k})}$ $\displaystyle={}$ $\displaystyle\frac{\partial}{\partial\theta(s^{k})}\left(\log[(E_{s,d})_{j}^{\top}\exp(\beta\gamma^{d}\Theta)]-\log[\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)]\right)$ $\displaystyle={}$ $\displaystyle\frac{\beta\gamma^{d}(E_{s,d})_{j,k}\exp(\beta\gamma^{d}\theta(s^{k}))}{(E_{s,d})_{j}^{\top}\exp(\beta\gamma^{d}\Theta)}-\frac{\beta\gamma^{d}\textbf{1}_{A}^{\top}E_{s,d}e_{k}\exp(\beta\gamma^{d}\theta(s^{k}))}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}$ $\displaystyle={}$ $\displaystyle\frac{\beta\gamma^{d}(E_{s,d}e_{k}\exp(\beta\gamma^{d}\theta(s^{k})))_{j}}{(E_{s,d})_{j}^{\top}\exp(\beta\gamma^{d}\Theta)}-\frac{\beta\gamma^{d}\textbf{1}_{A}^{\top}E_{s,d}e_{k}\exp(\beta\gamma^{d}\theta(s^{k}))}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}$ $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[\frac{e_{j}^{\top}}{e_{j}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}-\frac{\textbf{1}_{A}^{\top}}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\right]E_{s,d}e_{k}\exp(\beta\gamma^{d}\theta(s^{k})).$ $$

Hence,

$$ $\displaystyle[\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}]_{\cdot,k}=\beta\gamma^{d}\left[D(E_{s,d}\exp(\beta\gamma^{d}\Theta))^{-1}-(\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta))^{-1}\textbf{1}_{A}\textbf{1}_{A}^{\top}\right]E_{s,d}e_{k}\exp(\beta\gamma^{d}\theta(s^{k}))$ $$

From this, it follows that

$$ $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}=\beta\gamma^{d}\left[D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}-\textbf{1}_{A}\textbf{1}_{A}^{\top}\right]\frac{E_{s,d}D(\exp(\beta\gamma^{d}\Theta))}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}.$ (25) $$

The desired result is now easy to see.
∎

###### Proof.

#### A.1.8 Proof of Theorem 4.7 — Exponential variance decay of E- SoftTreeMax

There exists $\alpha\in\left(0,1\right)$ such that, for any function $Q:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},$

$$ $\operatorname{Var}\left(\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}(a|s)Q(s,a)\right)\in\mathcal{O}\left(\beta^{2}\gamma^{2d}\alpha^{2d}\right).$ $$

If all rewards are equal ($r\equiv\text{const}$), then $\alpha=|\lambda_{2}(P^{\pi_{b}})|$.

###### Proof.

Let $d\geq 2.$ Recall that

$$ $E_{s,d}=P_{s}\prod_{h=1}^{d-1}\left(D\left(\exp[\beta\gamma^{h}R]\right)P^{\pi_{b}}\right),$ (26) $$

and that $R$ refers to the $S$-dimensional vector whose $s$-th coordinate is $r(s).$
Define

$$ $B_{i}=\begin{cases}P^{\pi_{b}}&\text{ if }i=d-1,\\ D^{-1}(P^{\pi_{b}}M_{i+1})P^{\pi_{b}}D(M_{i+1})&\text{ if }i=1,\ldots,d-2,\end{cases}$ (27) $$

and the vector

$$ $M_{i}=\begin{cases}\exp(\beta\gamma^{d-1}R)&\text{ if }i=d,\\ \exp(\beta\gamma^{i}R)\circ P^{\pi_{b}}M_{i+1}&\text{ if }i=1,\ldots,d-2,\end{cases}$ (28) $$

where $\circ$ denotes the element-wise product.
Then,

$$ $E_{s,d}=P_{s}D(M_{1})\prod_{i=1}^{d-1}B_{i}.$ (29) $$

It is easy to see that each $B_{i}$ is a row-stochastic matrix, i.e., all entries are non-negative and $B_{i}\textbf{1}_{S}=\textbf{1}_{S}.$

Next, we prove that all non-zeros entries of $B_{i}$ are bounded away from 0 0 by a constant. This is necessary to apply the next result from (Chatterjee & Seneta, ). The $j$-th coordinate of $M_{i}$ satisfies

$$ $(M_{i})_{j}=\exp[\beta\gamma^{i}R_{j}]\sum_{k}[P^{\pi_{b}}]_{j,k}(M_{i+1})_{k}\leq\|\exp[\beta\gamma^{i}R]\|_{\infty}\|M_{i+1}\|_{\infty}.$ (30) $$

Separately, observe that $\|M_{d-1}\|_{\infty}\leq\|\exp(\beta\gamma^{d-1}R)\|_{\infty}.$ Plugging these relations in ([28](#A1.E28)) gives

$$ $\|M_{1}\|_{\infty}\leq\prod_{h=1}^{d-1}\|\exp[\beta\gamma^{h}R]\|_{\infty}=\prod_{h=1}^{d-1}\|\exp[\beta R]\|^{\gamma^{h}}_{\infty}=\|\exp[\beta R]\|_{\infty}^{\sum_{h=1}^{d-1}\gamma^{h}}\leq\|\exp[\beta R]\|_{\infty}^{\frac{1}{1-\gamma}}.$ (31) $$

Similarly, for every $1\leq i\leq d-1,$ we have that

$$ $\|M_{i}\|_{\infty}\leq\prod_{h=i}^{d-1}\|\exp[\beta R]\|^{\gamma^{h}}_{\infty}\leq\|\exp[\beta R]\|_{\infty}^{\frac{1}{1-\gamma}}.$ (32) $$

The $jk$-th entry of $B_{i}=D^{-1}(P^{\pi_{b}}M_{i+1})P^{\pi_{b}}D(M_{i+1})$ is

$$ $(B_{i})_{jk}=\frac{P^{\pi_{b}}_{jk}[M_{i+1}]_{k}}{\sum_{\ell=1}^{|S|}P^{\pi_{b}}_{j\ell}[M_{i+1}]_{\ell}}\geq\frac{P^{\pi_{b}}_{jk}}{\sum_{\ell=1}^{|S|}P^{\pi_{b}}_{j\ell}[M_{i+1}]_{\ell}}\geq\frac{P^{\pi_{b}}_{jk}}{\|\exp[\beta R]\|_{\infty}^{\frac{1}{1-\gamma}}}.$ (33) $$

Hence, for non-zero $P^{\pi_{b}}_{jk}$, the entries are bounded away from zero by the same. We can now proceed with applying the following result.

Now, by (Chatterjee & Seneta, , Theorem 5) (see also (14) in (Mathkar & Borkar, )), $\lim_{d\to\infty}\prod_{i=1}^{d-1}B_{i}$ exists and is of the form $\textbf{1}_{S}\mu^{\top}$ for some probability vector $\mu.$ Furthermore, there is some $\alpha\in(0,1)$ such that $\varepsilon(d):=\left(\prod_{i=1}^{d-1}B_{i}\right)-\textbf{1}_{S}\,\mu^{\top}$ satisfies

$$ $\left\|\varepsilon(d)\right\|=O(\alpha^{d}).$ (34) $$

Pick linearly independent vectors $w_{2},\ldots,w_{S}$ such that

$$ $\mu^{\top}w_{i}=0\mbox{ for }i=2,\ldots,d.$ (35) $$

Since $\sum_{i=2}^{S}\alpha_{i}w_{i}$ is perpendicular to $\mu$ for any $\alpha_{2},\ldots\alpha_{S}$ and because $\mu^{\top}\exp(\beta\gamma^{d}\Theta)>0,$ there exists no choice of $\alpha_{2},\ldots,\alpha_{S}$ such that $\sum_{i=2}^{S}\alpha_{i}w_{i}=\exp(\beta\gamma^{d}\Theta).$ Hence, if we let $z_{1}=\textbf{1}_{S}$ and $z_{i}=D(\exp(\beta\gamma^{d}\Theta))^{-1}w_{i}$ for $i=2,\ldots,S,$ then it follows that $\{z_{1},\ldots,z_{S}\}$ is linearly independent. In particular, it implies that $\{z_{1},\ldots,z_{S}\}$ spans $\mathbb{R}^{S}.$

Now consider an arbitrary unit norm vector $z:=\sum_{i=1}^{S}c_{i}z_{i}\in\mathbb{R}^{S}$ s.t. $\|z\|_{2}=1.$ Then,

$$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}z={}$ $\displaystyle\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}\sum_{i=2}^{S}c_{i}z_{i}$ (36) $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}E_{s,d}D(\exp(\beta\gamma^{d}\Theta))}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\sum_{i=2}^{S}c_{i}z_{i}$ (37) $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}E_{s,d}}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\sum_{i=2}^{S}c_{i}w_{i}$ (38) $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}\left[\textbf{1}_{S}\mu^{\top}+\varepsilon(d)\right]}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\sum_{i=2}^{S}c_{i}w_{i}$ (39) $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}\varepsilon(d)}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\sum_{i=2}^{S}c_{i}w_{i}$ (40) $\displaystyle={}$ $\displaystyle\beta\gamma^{d}\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}\varepsilon(d)D(\exp(\beta\gamma^{d}\Theta))}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}(z-c_{1}\textbf{1}_{S}),$ (41) $$

where ([36](#A1.E36)) follows from the fact that $\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}z_{1}=\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}\textbf{1}_{S}=0,$ ([37](#A1.E37)) follows from Lemma [4.6](#S4.Thmtheorem6), ([38](#A1.E38)) holds since $z_{i}=D(\exp(\beta\gamma^{d}\Theta))^{-1}w_{i},$ ([40](#A1.E40)) because $\mu$ is perpendicular $w_{i}$ for each $i,$ while ([41](#A1.E41)) follows by reusing $z_{i}=D(\exp(\beta\gamma^{d}\Theta))^{-1}w_{i}$ relation along with the fact that $z_{1}=\textbf{1}_{S}.$

From ([41](#A1.E41)), it follows that

$$ $\displaystyle\|\nabla_{\theta}\log\pi_{d,\theta}^{\text{E}}z\|\leq{}$ $\displaystyle\beta\gamma^{d}\|\varepsilon(d)\|\left\|\left[I_{A}-\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\right]\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\right\|\|D(\exp(\beta\gamma^{d}\Theta))\|\,\|z-c_{1}\textbf{1}_{S}\|$ (42) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(\|I_{A}\|+\|\textbf{1}_{A}(\pi_{d,\theta}^{\text{E}})^{\top}\|)\left\|\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\right\|\exp(\beta\gamma^{d}\max_{s}\theta(s))\|z-c_{1}\textbf{1}_{S}\|$ (43) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\left\|\frac{D\left(\pi_{d,\theta}^{\text{E}}\right)^{-1}}{\textbf{1}_{A}^{\top}E_{s,d}\exp(\beta\gamma^{d}\Theta)}\right\|\exp(\beta\gamma^{d}\max_{s}\theta(s))\|z-c_{1}\textbf{1}_{S}\|$ (44) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\left\|D^{-1}(E_{s,d}\exp(\beta\gamma^{d}\Theta))\right\|\exp(\beta\gamma^{d}\max_{s}\theta(s))\|z-c_{1}\textbf{1}_{S}\|$ (45) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\frac{1}{\min_{s}[E_{s,d}\exp(\beta\gamma^{d}\Theta]_{s}}\exp(\beta\gamma^{d}\max_{s}\theta(s))\|z-c_{1}\textbf{1}_{S}\|$ (46) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\frac{\exp(\beta\gamma^{d}\max_{s}\theta(s))}{\exp(\beta\gamma^{d}\min_{s}\theta(s))\min_{s}|M_{1}|}\|z-c_{1}\textbf{1}_{S}\|$ (47) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\frac{\exp(\beta\gamma^{d}\max_{s}\theta(s))}{\exp(\beta\gamma^{d}\min_{s}\theta(s))\exp(\beta\min_{s}r(s))}\|z-c_{1}\textbf{1}_{S}\|$ (48) $\displaystyle\leq{}$ $\displaystyle\beta\gamma^{d}\alpha^{d}(1+\sqrt{A})\exp(\beta[\max_{s}\theta(s)-\min_{s}\theta(s)-\min_{s}r(s)])\|z-c_{1}\textbf{1}_{S}\|.$ (49) $$

Lastly, we prove that $\|z-c_{1}\textbf{1}_{S}\|$ is bounded independently of $d.$ First, denote by $c=(c_{1},\dots,c_{S})^{\top}$ and $\tilde{c}=(0,c_{2},\dots,c_{S})^{\top}.$ Also, denote by $Z$ the matrix with $z_{i}$ as its $i$-th column. Now,

$$ $\displaystyle\|z-c_{1}\textbf{1}_{S}\|$ $\displaystyle=\|\sum_{i=2}^{S}c_{i}z_{i}\|$ (50) $\displaystyle=\|Z\tilde{c}\|$ (51) $\displaystyle\leq\|Z\|\|\tilde{c}\|$ (52) $\displaystyle\leq\|Z\|\|c\|$ (53) $\displaystyle=\|Z\|\|Z^{-1}z\|$ (54) $\displaystyle\leq\|Z\|\|Z^{-1}\|,$ (55) $$

where the last relation is due to $z$ being a unit vector. All matrix norms here are $l_{2}$-induced norms.

Next, denote by $W$ the matrix with $w_{i}$ in its $i$-th column. Recall that in ([35](#A1.E35)) we only defined $w_{2},\dots,w_{S}.$ We now set $w_{1}=\exp(\beta\gamma^{d}\Theta)$. Note that $w_{1}$ is linearly independent of $\{w_{2},\dots,w_{S}\}$ because of ([35](#A1.E35)) together with the fact that $\mu^{\top}w_{1}>0.$ We can now express the relation between $Z$ and $W$ by $Z=D^{-1}(\exp(\beta\gamma^{d}\Theta))W.$
Substituting this in ([55](#A1.E55)), we have

$$ $\displaystyle\|z-c_{1}\textbf{1}_{S}\|$ $\displaystyle\leq\|D^{-1}(\exp(\beta\gamma^{d}\Theta))W\|\|W^{-1}D(\exp(\beta\gamma^{d}\Theta))\|$ (56) $\displaystyle\leq\|W\|\|W^{-1}\|\|D(\exp(\beta\gamma^{d}\Theta))\|\|D^{-1}(\exp(\beta\gamma^{d}\Theta))\|.$ (57) $$

It further holds that

$$ $\|D(\exp(\beta\gamma^{d}\Theta))\|\leq\max_{s}\exp\left(\beta\gamma^{d}\theta(s)\right)\leq\max\{1,\exp[\beta\max_{s}\theta(s)])\},$ (58) $$

where the last relation equals $1$ if $\theta(s)<0$ for all $s.$ Similarly,

$$ $\|D^{-1}(\exp(\beta\gamma^{d}\Theta))\|\leq\frac{1}{\min_{s}\exp\left(\beta\gamma^{d}\theta(s)\right)}\leq\frac{1}{\min\{1,\exp[\beta\min_{s}\theta(s)])\}}.$ (59) $$

Furthermore, by the properties of the $l_{2}$-induced norm,

$$ $\displaystyle\|W\|_{2}$ $\displaystyle\leq\sqrt{S}\|W\|_{1}$ (60) $\displaystyle=\sqrt{S}\max_{1\leq i\leq S}\|w_{i}\|_{1}$ (61) $\displaystyle=\sqrt{S}\max\{\exp(\beta\gamma^{d}\Theta),\max_{2\leq i\leq S}\|w_{i}\|_{1}\}$ (62) $\displaystyle\leq\sqrt{S}\max\{1,\exp[\beta\max_{s}\theta(s)],\max_{2\leq i\leq S}\|w_{i}\|_{1})\}.$ (63) $$

Lastly,

$$ $\displaystyle\|W^{-1}\|$ $\displaystyle=\frac{1}{\sigma_{\min}(W)}$ (64) $\displaystyle\leq\left(\prod_{i=1}^{S-1}\frac{\sigma_{\max}(W)}{\sigma_{i}(W)}\right)\frac{1}{\sigma_{\min}(W)}$ (65) $\displaystyle=\frac{\left(\sigma_{\max}(W)\right)^{S-1}}{\prod_{i=1}^{S}\sigma_{i}(W)}$ (66) $\displaystyle=\frac{\|W\|^{S-1}}{|\det(W)|}.$ (67) $$

The determinant of $W$ is a sum of products involving its entries. To upper bound ([67](#A1.E67)) independently of $d,$ we lower bound its determinant by upper and lower bounds on the entries $[W]_{i,1}$ that are independent of $d,$ depending on their sign:

$$ $\min\{1,\exp[\beta\min_{s}\theta(s)])\}\leq[W]_{i,1}\leq\max\{1,\exp[\beta\max_{s}\theta(s)])\}.$ (68) $$

Using this, together with ([55](#A1.E55)), ([57](#A1.E57)), ([58](#A1.E58)), ([59](#A1.E59)), and ([63](#A1.E63)), we showed that $\|z-c_{1}\textbf{1}_{S}\|$ is upper bounded by a constant independent of $d.$ This concludes the proof.
∎

###### Proof.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - The behavior/expansion policy $\pi_b$ is crucial in the approach. The paper sets the expansion policy to uniform, but this may not be realistic. Even with pruning, uniform expansion seems suboptimal for exploration. Moreover, how realistic is it to have a behavior policy that induces an irreducible and aperiodic transition matrix?

- Theorem 4.8: Additional insights on why the error scales linearly with $d$ would be valuable.
soundness: 3
strengths: - The work introduces an innovative approach to integrating planning with policy search methods, supported by substantial theoretical analysis that highlights the benefits of this approach.
- The empirical results on Atari, using a GPU-based simulator, are highly promising.
summary: The paper introduces a novel method to reduce variance in Policy Gradient (PG) methods by integrating Tree Search (TS) with a differentiable parametric policy. By incorporating planning into the PG procedure, the authors propose "SoftTreeMax," presented in two variants: C (exp-Expectation) and E (Expectation-exp). The paper offers a theoretical analysis demonstrating how this method reduces variance concerning tree expansion policy and environment parameters. It also analyzes the soundness of using an estimated model for planning, showing that the gradient bias correlates with model approximation error. The practical utility of this approach is demonstrated through experiments on Atari, employing a GPU-based simulator that efficiently utilizes distributed nature for tree expansion.
weaknesses: - The presentation of the two versions of SoftTreeMax (E and C) is unbalanced. While it is beneficial to discuss both, the paper does not adequately represent each. For instance, the Atari experiments focus on C-SoftTreeMax, the empirical demonstration of variance reduction (Figure 1) pertains to the E-version, the theoretical analysis in Section 4.2 is solely for the E version, and the discussion involving the forward model in Section 4.3 is exclusively for C-SoftTreeMax. This uneven representation can make the paper difficult to follow and raises questions about the rationale for using different versions. It also gives the impression that the work is incomplete. Additionally, guidance on which version to use is lacking; although the authors provide a motivation related to risk-aversion/safety for one version, it is not explored in detail.

- In the experiments, exact expectations are considered instead of sample-based methods. This seems limiting, given the appeal of PG methods in sampling-based scenarios. The absence of finite-sample variance components is a significant omission.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: 1. Is this tree expansion limited to softmax parameterization?
2. Is the method designed only for discrete action space?
soundness: 3
strengths: 1. The paper presents a novel method that combines policy gradient techniques with tree search planning, offering a fresh perspective on reducing gradient variance in reinforcement learning.
2. The authors provide solid theoretical analysis, including variance bounds and proofs that show how the tree expansion policy affects variance reduction. They also address the gradient bias introduced by approximate models.
3. The experimental evaluation on Atari games shows significant reductions in gradient variance and improvements in performance, validating the effectiveness of the proposed methods.
summary: The paper introduces a novel approach that replaces logits by the score of a trajectory starting from that state-action. Authors provide solid theoretical results showing their methods reduces the variance of policy gradient approach and validate it by conducting experiments on Atari games.
weaknesses: 1. The paper primarily considers softmax parameterization for policies, which is restrictive, especially when considering environments with continuous action spaces.
2. The proposed methods rely on the model dynamcis, which need to be infer from the interactions. When employed on offline setting, this may introduce extra bias.
3. Tree expansion, especially with deeper trees, can be computationally intensive. The paper could benefit from a more detailed analysis of the computational costs and how they impact practical deployment.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Can you further explain how the proposed method is different from the AlphaZero/MuZero?
2. Why was PPO the only baseline?
soundness: 2
strengths: 1. The experiments show significant improvements over the chosen baseline.
2. The methodology is supported with theoretical results.
3. The paper implements a parallel version of BFS using GPUs that seems to be scalable.
summary: The paper aims to integrate a novel tree search methodology with policy gradient with the goal of reducing the variance and improving the performance of PG agents.
weaknesses: 1. The novelty of the methodology seems quite limited. Eq. (2) is supposed to be the logit of the policy but I cannot see any difference from the definition of a q-value function, which would entail that the paper is proposing a slight variation of AlphaZero.
2. The authors only compare against PPO. Given that the proposed algorithm is a tree search model-based algorithm, it would be more appropriate to compare against model-based methods, ideally MuZero.

---

confidence: 2
contribution: 3
initial_rating: 3
presentation: 3
questions: 1. In many cases (Sec B.3), the SoftTree max policies start with a lower score than PPO; why is that so?
2. Why did the performance on Krull decrease (PPO)?
3. How is your work related to [1]
4. Could you provide an explicit formula for calculating the logits with the full tree expansion?
5. Following footnote 1 on page 8. I am unsure if extending the proposed algorithm to stochastic environments is that easy.

[1] https://arxiv.org/abs/1710.11417
soundness: 1
strengths: 1. An Interesting and important question.
2. Comprehensive conceptual and theoretical analysis.
summary: The paper proposes SoftTreeMax, a novel policy gradient method that integrates tree search (TS) and policy gradient (PG) techniques to reduce the variance of policy gradients, a common issue in traditional PG methods. The SoftTreeMax approach uses a differentiable policy that extends standard softmax by incorporating planning, leading to improved sample efficiency and performance.  Theoretical analysis shows that the variance reduction depends on the choice of the tree expansion policy, with deeper tree expansions leading to lower variance. Furthermore, the authors provide bounds on the gradient bias when using approximate models.
weaknesses: I am much concerned about the empirical evaluations.
1. The wall time is much affected by implementational details. These should be, at the very least, appropriately discussed.
	1. For example, [1] reports very high fps, exceeding what is obtained in the paper.
2. I do not see details of the network used. 
3. It is not clear what the pruning is and how it affects training
4. **important**: It is not clear if the advantage of the proposed method stems from the variance reduction (as claimed) or increased computations per action. E.g., what would happen if the baseline had a bigger network? 
5. The algorithm is a model-based one; thus, having a baseline from this realm is also desirable.

The literature on embedding search as an inductive bias is quite broad and is completely missing in the related work section. Eg. value iteration networks, A3Tree etc.

Meta-review: This paper proposed and analyzed a softmax-linear policy parameterization with an interesting feature design that depends on the behavioral policy that generate the data and a tree search approach. Two methods called C-Soft-TreeMax and E-Soft-TreeMax have been proposed. Though the paper has provided interesting preliminary experimental results, the theoretical results are not convincing enough. In particular, as the main motivation of the new PG method is to reduce the variance, the $S^2A^2$ dependence in Theorem 4.4 and the $S$ dependence in 4.8 do not seem to support this motivation. In fact, even the variance bound for naive REINFORCE estimator does not have such dependence. Given the empirical bounds in the experiments, this suggests that the theoretical analysis of variance bound for Soft-TreeMax should be improved. 

Though the paper has a good potential after fixing the theoretical issues, we decide to reject this paper for this year's ICLR.

Decision: Reject