RVI-SAC:
Average Reward Off-Policy Deep Reinforcement Learning

We define the interaction between the environment and the agent as a Markov Decision Process (MDP) $\mathcal{M}=(\mathcal{S},\mathcal{A},r,p)$. Here, $s\in\mathcal{S}$ represents the state space, $a\in\mathcal{A}$ represents the action space, $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R},|r(\cdot,\cdot)|\leq\|r\|_{\infty}$ is the reward function, and $p:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$ is the state transition function. At each discrete time step $t=0,1,2,\ldots$, the agent receives a state $S_{t}\in\mathcal{S}$ from the MDP and selects an action $A_{t}\in\mathcal{A}$. The environment then provides a reward $R_{t}=r(S_{t},A_{t})$ and the next state $S_{t+1}\in\mathcal{S},$ repeating this process. The state transition function is defined for all $s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}$ as $p\left(s^{\prime}\mid s,a\right):=\operatorname{Pr}\left(S_{t+1}=s^{\prime}\mid S_{t}=\right.$ $\left.s,A_{t}=a\right)$. Furthermore, we use a stationary Markov policy $\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ as the criterion for action selection. This represents the probability of selecting an action $a\in\mathcal{A}$ given a state $s\in\mathcal{S}$ and is defined as $\pi(a|s):=\operatorname{Pr}\left(A_{t}=a\mid S_{t}=s\right)$.

To simplify the discussion that follows, we make the following assumption for the MDPs where average reward reinforcement learning is applied:

Under this assumption, for any policy $\pi$, a stationary state distribution $d_{\pi}(s)$ exists. The distribution including actions is denoted as $d_{\pi}(s,a)=d_{\pi}(s)\pi(s|a)$.

The average reward for a policy $\pi$ is defined as:

The optimal policy in average reward criterion is defined as:

The Q function for average reward reinforcement learning is defined as:

The optimal Bellman equation for average reward is as follows:

From existing research (e.g., Puterman (1994)), it is known that this equation has the following properties:

• •

  There exists a unique solution for $\rho$ as $\rho=\rho^{\pi^{*}}$.

• •

  There exisits a unique solution only up to a constant $c\in\mathbb{R}$ for $Q(s,a)$ as $q(s,a)=Q^{\pi^{*}}(s,a)+c$.

• •

  For the solution $Q$ to the equation, a deterministic policy $\mu(s)=\operatorname*{arg\,max}_{a}q(s,a)$ is one of the optimal policies.

Henceforth, we denote $\rho^{\pi^{*}}$ as $\rho^{*}$.

RVI Q-learning (Konda & Borkar, 1999; Wan et al., 2020) is one of the average reward reinforcement learning methods for the tabular Q function, and updates the Q function as follows:

From the convergence proof of generalized RVI Q-learning (Wan et al., 2020), the function $f$ can be any function that satisfies the following assumption:

In practice, $f$ often takes forms such as $f(Q)=Q(S,A),\max_{a}Q(S,a)$ using arbitrary state/action pair $(S,A)$ as the Reference State, or the sum over all state/action pairs, $f(Q)=g\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}Q(s,a),g\sum_{s\in\mathcal{S}}\max_{a}Q(s,a)$, with gain $\forall g>0$. This assumption plays an important role in demonstrating the convergence of the algorithm. Intuitively, this indicates that the function $f$, satisfying this assumption, can include functions that correspond to specific elements of the vector $x$ or their weighted linear sum.

This algorithm, under certain appropriate assumptions, converges almost surely to a unique solution $q^{*}$, and it has been shown that $q^{*}$ satisfies both the optimal Bellman equation (Equation 4) and

as demonstrated in Wan et al. (2020).

We extend the RVI Q-learning algorithm described in Equation 5 to an updating method for the Q function represented by a Neural Network. Following traditional approach in Neural Network-based Q-learning, we update the parameters $\phi$ of the Q-Network $Q_{\phi}$ using the target:

and by minimizing the following loss function:

$\mathcal{B}$ is a mini-batch uniformly sampled from the Replay Buffer $\mathcal{D}$, which accumulates experiences $(S_{t},A_{t},R_{t},S_{t+1})$ obtained during training, and $\phi^{\prime}$ are the parameters of the target network (Mnih et al., 2013).

In implementing this method, we need to consider the following two points:

The first point is the choice of function $f$. As mentioned in Section 2.3, tabular RVI Q-learning typically uses a Reference State $(S,A)\in\mathcal{S}\times\mathcal{A}$ or the sum over all state/action pairs to calculate $f(Q)$. Using the Reference State is easily applicable to problems with continuous state/action spaces in Neural Network-based methods. However, concerns arise about performance dependency on the visitation frequency to the Reference State and the accuracy of its Q-value (Wan et al., 2020). On the other hand, calculating the sum over all state/action pairs does not require a Reference State but is not directly computable with Neural Networks for $f(Q_{\phi^{\prime}})$. To address these issues, we substitute $f(Q_{\phi^{\prime}})$ with $f(Q_{\phi^{\prime}};\mathcal{B})$, calculated using mini-batch $\mathcal{B}$, as shown in Equation 6:

Equation 6 serves as an unbiased estimator of $f(Q_{\phi^{\prime}})$ when set as:

where $b$ represents the behavior policy in off-policy methods, and $d_{b}(\cdot)$ denotes the stationary state distribution under the behavior policy $b$. In our method, we use settings as shown in Equations 6 and 7, but this discussion is applicable to any setting that satisfies:

for the random variable $X_{t}$. Thus, the target value used for the Q-Network update becomes:

The second point is that the variance of the sample value $f(Q_{\phi^{\prime}};\mathcal{B})$ (Equation 6) can increase the variance of the target value (Equation 9), potentially leading to instability in learning. This issue is pronounced when the variance of the Q-values is large. A high variance in Q-values can potentially lead to an increase in the variance of the target values, creating a feedback loop that might further amplify the variance of Q-values. To mitigate the variance of the target value, we propose the Delayed f(Q) Update technique. Delayed f(Q) Update employs a value $\xi_{t}$, updated as follows, instead of using $f(Q_{\phi^{\prime}};\mathcal{B})$ for calculating the target value:

$\beta_{t}$ denotes the learning rate for $\xi_{t}$. The new target value using $\xi_{t}$ is then:

In this case, $\xi_{t}$ serves as a smoothed value of $f(Q_{\phi^{\prime}};\mathcal{B})$, and this update method is expected to reduce the variance of the target value.

Theoretical Analysis of Delayed f(Q) Update

We reinterpret the Q-Network update method using Delayed f(Q) Update in the context of a tabular Q-learning algorithm, it can be expressed as follows:

This update formula is a specialization of asynchronous stochastic approximation (SA) on two time scales (Borkar, 1997; Konda & Borkar, 1999). By selecting appropriate learning rates such that $\frac{\alpha_{t}}{\beta_{t}}\rightarrow 0$, the update of $\xi_{t}$ in Equation 10 can be considered faster relative to the update of $Q_{t}$. Therefore, since $\xi_{t}$ can be considered a “relative constant”, it can be viewed as being equivalent to $f(Q_{t})$. The convergence of this algorithm is discussed in Appendix C and summarized in Theorem 3.1:

We propose a policy update method for the average reward criterion, inspired by the policy update method of the SAC(Haarnoja et al., 2018a, b).

In the SAC, a soft-Q function defined for the discount rate $\gamma\in(0,1)$ and a policy $\pi$ (Haarnoja et al., 2017):

The policy is then updated in the following manner for $\forall s\in\mathcal{S}$:

The partition function $Z^{\pi_{\text{old}}}(s)$ normalizes the distribution and can be ignored in the gradient of the new policy (refer to Haarnoja et al. (2018a)). $\Pi$ represents the set of policies, such as a parametrized family like Gaussian policies. According to the soft policy improvement theorem (Haarnoja et al., 2018a, b), for the updated policy $\pi_{\text{new}}$, the condition $Q^{\pi_{\text{new}},\gamma}(s,a)\geq Q^{\pi_{\text{old}},\gamma}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A}$ holds, indicating policy improvement. The actor’s update rule in the SAC is constructed based on this theorem. Further, defining the entropy-augmented reward $R_{t}^{\text{ent}}:=R_{t}-\mathbb{E}_{s^{\prime}\sim p(\cdot|S_{t},A_{t}),a^{\prime}\sim\pi(\cdot|s^{\prime})}{\left[\log\pi(a^{\prime}|s^{\prime})\right]}$, the Q function in Equation 11 can be reformulated as $Q^{\pi,\gamma}(s,a):=\mathbb{E}_{\pi}{\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}^{\text{ent}}|S_{0}=s,A_{0}=a\right]}$, allowing the application of the standard discounted Q-learning framework for the critic’s update (Haarnoja et al., 2018a, b).

In the context of average reward reinforcement learning, the soft average reward is defined as:

Correspondingly, the average reward soft-Q function is defined as:

From Equation 14, the soft Q function represents the expected cumulative sum of rewards minus the average reward. Thus, the relationship $Q^{\pi_{\text{new}}}(s,a)\geq Q^{\pi_{\text{old}}}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A}$ in the policy improvement theorem for the discounted SAC does not guarantee policy improvement. We present a new average reward soft policy improvement theorem using the soft average reward $\rho^{\pi}_{\text{soft}}$ as a metric.

This result demonstrates that updating the policy in the same manner as SAC leads to improvements in the policy under the average reward criterion. Additionally, defining the entropy-augmented reward $R_{t}^{\text{ent}}$ and the entropy-augmented Q function $Q^{\pi,\text{ent}}(s,a)$ as

allows the Q function in Equation 14 to be reformulated as $Q^{\pi,\text{ent}}(s,a):=\mathbb{E}_{\pi}{\left[\sum_{t=0}^{\infty}R_{t}^{\text{ent}}-\rho^{\pi}_{\text{soft}}|S_{0}=s,A_{0}=a\right]}$. This formulation aligns with the definition of the Q function in average reward reinforcement learning (Equation 3), enabling the application of the average reward Q-learning framework.

In this section, we address the challenge associated with applying the average reward criterion to tasks that are not purely continuing tasks, such as locomotion tasks where episodes may end due to falls. Average reward reinforcement learning assumes continuing tasks that do not have an episode termination. This is because average rewards are defined over the infinite horizon, and after the end of an episode, the agent continues to receive a reward of zero, leading to an average reward of zero. However, in many tasks, such as locomotion tasks, episodes may end due to events like robot falls, depending on the policy. In these cases, the tasks are not purely continuing.

To apply average reward reinforcement learning to such tasks, we employ the environment reset and the Reset Cost which ATRPO (Zhang & Ross, 2021) does. The environment reset regards a terminated episode as a continuing one by initializing the environment. Reset Cost is the penalty reward given for resetting the environment, denoted as $-r_{\text{cost}}$ (where $r_{\text{cost}}>0$). This means that, even after an episode ends in a certain terminal state $S_{t}$, initializing the environment, and observing the initial state $S_{0}$, the experience $(S_{t-1},A_{t-1},r(S_{t-1},A_{t-1})-r_{\text{cost}},S_{0})$ is obtained, and the episode is treated as continued.

In ATRPO, for experiments in the Mujoco environment, the Reset Cost $r_{\text{cost}}$ is fixed at 100, but the optimal Reset Cost is generally non-trivial. Instead of setting the $r_{\text{cost}}$, we propose a method to control the frequency at which the agent reaches termination states. Let’s consider a new MDP from MDPs with termination, where we only introduce environment resets without adding the Reset Cost (equivalent to the environment when $r_{\text{cost}}=0$). Let $\mathcal{S}_{\text{term}}$ be the set of termination states in the original MDP, and define the frequency $\rho_{\text{reset}}^{\pi}$ at which the agent reaches termination states under the policy $\pi$ as follows:

Using $\rho_{\text{reset}}^{\pi}$, we consider the following constrained optimization problem:

This problem aims to maximize the average reward $\rho^{\pi}$ with a constraint on the frequency of reaching termination states, where the termination frequency target $\epsilon_{\text{reset}}\in(0,1)$ is a user parameter. Note that $\rho^{\pi}$ here refers to the average reward when the Reset Cost is set to zero.

To solve this constrained optimization problem, we define the Lagrangian for the dual variable $\lambda$ as follows:

Following prior research in constrained optimization problems, the primal problem is formulated as:

In our approach to solving this problem, similar to the adjustment of the temperature parameter in Maximum Entropy Reinforcement Learning (Haarnoja et al., 2018b; Abdolmaleki et al., 2018), we alternate between outer and inner optimization steps. The outer optimization step is updating $\pi$ to maximize $\rho^{\pi}-\lambda\rho_{\text{reset}}^{\pi}$ for a fixed $\lambda$. Since $\rho^{\pi}-\lambda\rho_{\text{reset}}^{\pi}$ is equal to the average reward when $r_{\text{cost}}=\lambda$, this optimization step is equivalent to the policy update step in average reward reinforcement learning with Reset Cost. The inner optimization step is updating $\lambda$ to minimize $-\lambda\rho_{\text{reset}}^{\pi}-\lambda\epsilon_{\text{reset}}$. To compute this objective, it is necessary to obtain $\rho_{\text{reset}}^{\pi}$. Hence, we estimate the value of $\rho_{\text{reset}}^{\pi}$ by updating the Q function $Q_{\text{reset}}$ under the setting $r(s,a)={{\mathbb{E}}}_{\begin{subarray}{c}s^{\prime}\sim p(\cdot|s,a)\end{subarray}}\left[\mathbbm{1}\left(s^{\prime}\in\mathcal{S}_{\text{term}}\right)\right]$ using the update method described in Section 3.1.

We conducted experiments with 10 different random seed trials for each algorithm, sampling evaluation scores every 5,000 steps. For RVI-SAC and SAC, stochastic policies are treated as deterministic during evaluation. The maximum episode step is limited to 1,000 during training and evaluation. Figure 1 shows the learning curves of RVI-SAC, SAC with various discount rates, and ARO-DDPG. These experiments set the evaluation score as the total return over 1,000 steps. Results of experiments with the evaluation score set as an average reward (total_return / survival_step) are presented in Appendix F.1.

From the results shown in Figure 1, when comparing RVI-SAC with SAC with various discount rates, RVI-SAC demonstrates equal or better performance than SAC with the best discount rate in all environments except HalfCheetah. A notable observation is from the Swimmer environment experiments (Figure 1(a)). SAC’s recommended discount rate of $\gamma=0.99$ (Haarnoja et al., 2018a, b) performs better than the other rates in environments other than Swimmer. However, a larger discount rate of $\gamma=0.999$ is required in the Swimmer environment. However, setting a large discount rate can lead to destabilization of learning and slow convergence (Fujimoto et al., 2018; Dewanto & Gallagher, 2021), and indeed, in the environments other than Swimmer, a setting of $\gamma=0.999$ shows lower performance. Compared to SAC, RVI-SAC shows the same performance as SAC ($\gamma=0.999$) in the Swimmer environment and equal or better than SAC ($\gamma=0.99$) in the other environments. This result suggests that while traditional SAC using a discount rate may be significantly impacted by the choice of discount rate, RVI-SAC using the average reward resolves this issue.

When comparing RVI-SAC with ARO-DDPG, RVI-SAC shows higher performance in all environments. SAC has improved performance over methods using deterministic policies by introducing the concept of Maximum Entropy Reinforcement Learning. Similarly, it can be considered that the introduction of this concept to RVI-SAC is the primary reason for RVI-SAC’s superior performance over ARO-DDPG.

In the previous section, we demonstrated that RVI-SAC overall exhibits better performance compared to SAC using various discount rates and ARO-DDPG. In this section, we show how each component of RVI-SAC contributes to the overall performance.

Performance Comparison of RVI-SAC, SAC with automatic Reset Cost adjustment and ARO-DDPG with automatic Reset Cost adjustment

Since RVI-SAC introduces the automatic Reset Cost adjustment, RVI-SAC uses a different reward structures from that used in SAC and ARO-DDPG in which the reward is set to zero after termination. To compare the performance of RVI-SAC, SAC and ARO-DDPG under the same reward structure, we conduct comparative experiments with RVI-SAC, SAC with the automatic Reset Cost adjustment (SAC with Reset) and ARO-DDPG with the automatic Reset Cost adjustment(ARO-DDPG with Reset). Figure 2(a) shows the learning curves of these experiments in the Ant environment. (Results for other environments are shown in Appendix F.2). Here, the discount rate of SAC is set to $\gamma=0.99$.

Figure 2(a) demonstrates that RVI-SAC outperforms SAC with automatic Reset Cost adjustment and ARO-DDPG with automatic Reset Cost adjustment. This result suggests that the improved performance of RVI-SAC is not solely due to the different reward structure but also due to the effects of using the average reward criterion.

Ablation Study of Delayed f(Q) Update

In this section, we evaluate the effectiveness of the Delayed f(Q) Update described in Section 3.1. This method stabilizes learning without depending on a specific state/action pair for updating the Q function. To validate the effectiveness of this method, we examine whether the followings are correct: (1) When the function $f(Q)$ is $f(Q)=Q(S,A)$ for state/action pair $(S,A)\in\mathcal{S}\times\mathcal{A}$, the performance depends on the choice of $(S,A)$. (2) When the Q function is updated using Equation 6 directory as $f(Q)$, learning becomes unstable. To examine these, we conducted performance comparisons with three algorithms: (1) RVI-SAC, (2) RefState $(s,a)-\#1,(s,a)-\#2$ and $(s,a)-\#3$ that are RVI-SACs updating the Q functions with $f(Q)=Q(s,a)$, using sampled state/action pairs, $(s,a)-\#1,(s,a)-\#2$ and $(s,a)-\#3$, as Reference States obtained from when agent takes random actions, respectively, (3) RVI-SAC without Delay that is RVI-SAC updating the Q function using Equation 6 directory as $f(Q)$.

Figure 2(b) shows the learning curves for these methods in the Ant environment. Firstly, comparing RVI-SAC with RefState $(s,a)-\#1,(s,a)-\#2$ and $(s,a)-\#3$, except for RefState $(s,a)-\#1$, the methods using Reference States show lower performance than RVI-SAC. Furthermore, comparing the results of RefState $(s,a)-\#1,(s,a)-\#2$ and $(s,a)-\#3$, it suggests that performance depends on the choice of Reference State. These results suggest the effectiveness of RVI-SAC, which shows good performance without depending on a specific state/action pair. Next, comparing RVI-SAC with RVI-SAC without Delay, which directly uses Equation 6, it is observed that RVI-SAC performs significantly better. This result suggests that, in RVI-SAC, implementing the Delayed f(Q) Update contributes to stabilizing the learning process, thereby achieving higher performance. It indicates the effectiveness of the Delayed f(Q) Update, aiming at stabilizing updates of the Q-function.

RVI-SAC with Fixed Reset Cost

To demonstrate the effectiveness of the Automatic Reset Cost Adjustment, we compare the performance of RVI-SAC and RVI-SAC with fixed Reset Costs in the Ant environment. Figure 2(c) shows the learning curves of RVI-SAC and RVI-SAC with fixed Reset Costs, $r_{\text{cost}}=0,10,100,250,500$. These results show that settings other than the optimal fixed Reset Cost of $r_{\text{cost}}=10$ for this environment decrease performance. Moreover, the performance of RVI-SAC with fixed Reset Costs is highly dependent on its setting. This result suggests the effectiveness of the automatic adjustment of Reset Cost, which does not require specific settings.