Actor Prioritized Experience Replay

Baturay SaglamFurkan B. MutluDogan Can ÇiçekSuleyman S. Kozat

article2023JAIR57 citations

Explains why standard prioritized experience replay fails in off-policy actor-critic continuous control and introduces LA3P, a replay prioritization framework that improves policy gradient accuracy by training the actor network on low temporal-difference error transitions.

Listen

Deep reinforcement learning enables autonomous agents to learn complex decision-making through trial and error by storing and reusing past experiences from a replay buffer. While prioritizing experiences with high temporal-difference (TD) error—known as Prioritized Experience Replay (PER)—substantially boosts performance in discrete action tasks like video games, it consistently degrades performance in continuous control domains like robotics. In continuous settings, actor-critic architectures must be used, but standard prioritization frequently leads to unstable training and suboptimal policies.

The article investigates the root theoretical causes behind this failure and proposes a novel sampling framework, termed Loss-Adjusted Approximate Actor Prioritized Experience Replay (LA3P). The study evaluates how scheduling different experience distributions for the actor (policy) and critic (value estimator) networks, combined with corrected loss functions, can restore and enhance the benefits of prioritization in continuous control.

The authors develop a mathematical proof showing that high TD errors in the critic directly increase value estimation errors, causing the calculated actor policy gradients to diverge from the true optimal gradient. To solve this, the proposed LA3P framework introduces inverse prioritized sampling, which supplies the actor network with low TD error transitions that the critic understands reliably. To preserve theoretical consistency and learning stability between the networks, LA3P allocates a fraction of each batch (typically 50%) to uniformly sampled experiences shared by both actor and critic. Furthermore, the framework integrates modified loss functions—the Huber loss and Prioritized Approximate Loss—to eliminate outlier bias caused by standard mean-squared error updates.

Key findings show that LA3P significantly outperforms standard actor-critic baselines (Soft Actor-Critic and Twin Delayed DDPG), vanilla PER, and competing correction methods across challenging continuous control benchmarks (MuJoCo and Box2D). Pairwise statistical tests confirmed that these performance gains are statistically significant (p < 0.05) across most complex environments, such as HalfCheetah, Ant, Hopper, and Swimmer. Ablation studies demonstrated that the shared uniform sampling component is the single most critical factor for maintaining stability, and a 50-50 split between uniform and prioritized/inverse-prioritized sampling consistently yields peak performance without requiring environment-specific tuning.

These results provide a clear blueprint for engineering more stable and data-efficient continuous control systems. The findings demonstrate that actor-critic architectures cannot treat experience sampling identically for policy generation and value estimation. By mitigating policy gradient divergence and eliminating outlier bias, organizations deploying continuous reinforcement learning can achieve faster convergence and higher final performance, lowering the compute time and sample collection costs associated with training complex models.

Practitioners looking to implement prioritization in continuous control should adopt the LA3P sampling framework with a default uniform batch fraction of 0.5 and the specified Huber and approximate loss corrections. Future research should investigate alternative shared sampling distributions aimed at variance reduction and evaluate the approach across real-world robotic systems and broader continuous-action applications.

The findings are supported by comprehensive theoretical derivations and rigorous statistical benchmarking over multiple random seeds. A minor limitation is that LA3P incurs a higher computational runtime due to maintaining additional tree data structures for inverse sampling, though parallel single-instruction multiple-data (SIMD) operations on modern hardware substantially mitigate this overhead. Readers can have high confidence in the algorithm's performance advantages in simulated continuous control benchmarks.

Bilkent University Yale University Actor Prioritized Experience Replay off-policy actor-critic methods experience replay algorithm

arXiv: 2209.00532

Paper: Prioritized Experience Replay, Tom Schaul et al. (2016). Introduces the foundational Prioritized Experience Replay (PER) mechanism using temporal-difference error that the target paper directly investigates and modifies for continuous actor-critic control.
Paper: Addressing Function Approximation Error in Actor-Critic Methods, Scott Fujimoto et al. (2018). Presents Twin Delayed Deep Deterministic Policy Gradient (TD3), one of the primary continuous actor-critic baseline architectures evaluated and stabilized in the target work.
Paper: Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor, Tuomas Haarnoja et al. (2018). Establishes Soft Actor-Critic (SAC), a core continuous actor-critic algorithm that serves as a primary benchmark and foundation for LA3P's sampling corrections.
Paper: Continuous control with deep reinforcement learning, T. Lillicrap et al. (2015). Provides the foundational deep deterministic policy gradient framework for continuous control that underpins modern deep actor-critic methods and their experience replay dynamics.
Paper: Deterministic Policy Gradient Algorithms, David Silver et al. (2014). Derives the theoretical foundations of deterministic policy gradients and off-policy actor-critic architectures analyzed in the target paper's policy gradient divergence proofs.
Paper: Actor-Critic Algorithms, Vijay Konda et al. (1999). Establishes the two-time-scale convergence framework between actor policy updates and critic value estimation that informs how distinct sampling distributions affect learning stability.
Paper: Self-improving reactive agents based on reinforcement learning, planning and teaching, Longxin Lin (1992). Introduces the fundamental concept and utility of experience replay in connectionist reinforcement learning.

No sufficiently relevant recommendations were found.

Cover for Actor Prioritized Experience Replay

Abstract

A widely-studied deep reinforcement learning (RL) technique known as Prioritized Experience Replay (PER) allows agents to learn from transitions sampled with non-uniform probability proportional to their temporal-difference (TD) error. Although it has been shown that PER is one of the most crucial components for the overall performance of deep RL methods in discrete action domains, many empirical studies indicate that it considerably underperforms off-policy actor-critic algorithms. We theoretically show that actor networks cannot be effectively trained with transitions that have large TD errors. As a result, the approximate policy gradient computed under the Q-network diverges from the actual gradient computed under the optimal Q-function. Motivated by this, we introduce a novel experience replay sampling framework for actor-critic methods, which also regards issues with stability and recent findings behind the poor empirical performance of PER. The introduced algorithm suggests a new branch of improvements to PER and schedules effective and efficient training for both actor and critic networks. An extensive set of experiments verifies our theoretical findings, showing that our method outperforms competing approaches and achieves state-of-the-art results over the standard off-policy actor-critic algorithms.

Keywords

Actor Prioritized Experience Replay off-policy actor-critic methods experience replay algorithm stochastic prioritization proportional prioritization policy optimization continuous control benchmarks deep reinforcement learning

1. Introduction
2. Related Work
3. Technical Preliminaries
3.1 Deep Reinforcement Learning
3.2 Prioritized Experience Replay
4. Prioritized Sampling in Actor-Critic Algorithms
5. Adaptation of Prioritized Experience Replay to Actor-Critic Algorithms
5.1 Inverse Sampling for the Actor Network
5.2 Optimizing the Actor and Critic with a Shared Set of Transitions
6. Experiments
6.1 Experimental Details
6.2 Comparative Evaluation
6.3 Ablation Studies
7. Conclusion
Acknowledgments
Appendix A. Summary of the LA3P Framework
Appendix B. Experimental Details
B.1 Architecture and Hyperparameter Setting
B.2 Implementation
B.3 Experimental Setup
Appendix C. Empirical Complexity Analysis
References

Knowls

Knowl 1 — Policy Gradient Divergence Under High TD Error Transitions
theoretical result
In off-policy actor-critic reinforcement learning, optimizing an actor network with transitions that exhibit large temporal-difference (TD) errors causes the computed policy gradient to deviate and diverge from the true policy gradient under the optimal action-value function $Q^\pi$ .

Let a transition tuple be $\tau_i = (s_i, a_i, r_i, s_{i+1})$ . The temporal-difference error associated with a critic network $Q_\theta$ is defined as: $\delta_\theta(\tau_i) = r_i + \gamma Q_\theta(s_{i+1}, a_{i+1}) - Q_\theta(s_i, a_i)$ where $a_{i+1} \sim \pi_\phi(s_{i+1})$ is the action chosen by policy $\pi_\phi$ , and $\gamma \in [0, 1)$ is the discount factor. Under the optimal action-value function $Q^\pi$ , the true TD error is zero: $\delta^\pi(\tau_i) = r_i + \gamma Q^\pi(s_{i+1}, a_{i+1}) - Q^\pi(s_i, a_i) = 0$ Subtracting the true TD error yields: $\delta_\theta(\tau_i) = \gamma \left( Q_\theta(s_{i+1}, a_{i+1}) - Q^\pi(s_{i+1}, a_{i+1}) \right) - \left( Q_\theta(s_i, a_i) - Q^\pi(s_i, a_i) \right) = \gamma \epsilon_{\tau_{i+1}} - \epsilon_{\tau_i}$ where $\epsilon_{\tau_i}$ and $\epsilon_{\tau_{i+1}}$ denote the Q-value estimation errors at steps $i$ and $i+1$ .

Under deep function approximation, the computed policy gradient $\nabla_\phi(\tau_i)$ and true policy gradient $\nabla_\phi^{\text{true}}(\tau_i)$ are given by: $\nabla_\phi(\tau_i) = k Q_\theta(s_i, a_i), \quad \nabla_\phi^{\text{true}}(\tau_i) = k Q^\pi(s_i, a_i)$ where $k = d^\pi(s_i) \frac{\partial \pi(s_i, a_i)}{\partial \phi}$ , and $d^\pi(s) = \sum_{t=0}^\infty \gamma^t p(s_t = s \mid s_0, \pi)$ is the discounted state distribution. The policy gradient discrepancy is directly proportional to the estimation error: $|\nabla_\phi(\tau_i) - \nabla_\phi^{\text{true}}(\tau_i)| = |k \epsilon_{\tau_i}| = k |\epsilon_{\tau_i}| \propto |\epsilon_{\tau_i}|$

Because an increase in the absolute TD error $|\delta_\theta(\tau_i)|$ can increase the absolute Q-value estimation error $|\epsilon_{\tau_i}|$ or $|\epsilon_{\tau_{i+1}}|$ , prioritizing transitions with large TD errors causes the approximate policy gradient to diverge from the true policy gradient at step $i$ or $i+1$ . Consequently, actor networks should be trained on low TD error transitions.
Knowl 2 — Loss-Adjusted Approximate Actor Prioritized Experience Replay Algorithm
algorithm
Loss-Adjusted Approximate Actor Prioritized Experience Replay (LA3P) is an off-policy actor-critic prioritization algorithm that optimizes critic networks on high temporal-difference (TD) error transitions, optimizes actor networks on low TD error transitions via inverse prioritized sampling, and trains both networks on a shared mini-batch of uniformly sampled transitions to preserve actor-critic coupling and learning stability.
Input: Mini-batch size $N$ , prioritization exponent $\alpha$ , importance sampling exponent $\beta$ , uniform sampling fraction $\lambda \in [0, 1]$ , target step-size $\zeta$ , actor step-size $\eta_\pi$ , critic step-size $\eta_Q$ , total training steps $T$
Initialize actor $\pi_\phi$ and critic $Q_\theta$ networks with parameters $\phi, \theta$
Initialize target networks $\phi' \leftarrow \phi, \theta' \leftarrow \theta$
Initialize initial priority $p_{\text{init}} = 1$ and replay buffer $R = \emptyset$
for $t = 1$ to $T$ do
    Select action $a_t \sim \pi_\phi(s_t)$ , observe reward $r_t$ and next state $s_{t+1}$
    Store transition $\tau_t = (s_t, a_t, r_t, s_{t+1})$ in $R$ with priority $p_t = p_{\text{init}}$
    for each update step do
        Uniformly sample mini-batch $I_{\text{uni}} \sim p(\tau_i) = \frac{1}{|R|}$ with $|I_{\text{uni}}| = \lambda \cdot N$
        Compute PAL loss $L_{\text{PAL}}(\delta_\theta(\tau_i))$ for $i \in I_{\text{uni}}$
         $\theta \leftarrow \theta - \eta_Q \cdot \frac{1}{|I_{\text{uni}}|} \sum_{i \in I_{\text{uni}}} \nabla_\theta L_{\text{PAL}}(\delta_\theta(\tau_i))$
        Compute policy gradient $\nabla_\phi(\tau_i)$ for $i \in I_{\text{uni}}$
         $\phi \leftarrow \phi + \eta_\pi \cdot \frac{1}{|I_{\text{uni}}|} \sum_{i \in I_{\text{uni}}} \nabla_\phi(\tau_i)$
        Update priorities $p(\tau_i) \leftarrow \max(|\delta_\theta(\tau_i)|^\alpha, 1)$ for $i \in I_{\text{uni}}$
         $\theta' \leftarrow \zeta \theta + (1 - \zeta)\theta', \quad \phi' \leftarrow \zeta \phi + (1 - \zeta)\phi'$
        Sample mini-batch for critic via prioritized sampling $I_{\text{pri}} \sim p(\tau_i) = \frac{\max(|\delta_\theta(\tau_i)|^\alpha, 1)}{\sum_j \max(|\delta_\theta(\tau_j)|^\alpha, 1)}$ with $|I_{\text{pri}}| = (1 - \lambda) \cdot N$
         $\theta \leftarrow \theta - \eta_Q \cdot \frac{1}{|I_{\text{pri}}|} \sum_{i \in I_{\text{pri}}} \nabla_\theta L_{\text{Huber}}(\delta_\theta(\tau_i))$
        Update priorities $p(\tau_i) \leftarrow \max(|\delta_\theta(\tau_i)|^\alpha, 1)$ for $i \in I_{\text{pri}}$
        Sample mini-batch for actor via inverse prioritized sampling $I_{\text{inv}} \sim \tilde{p}(\tau_i) = \frac{p_{\max}}{p(\tau_i)}$ with $|I_{\text{inv}}| = (1 - \lambda) \cdot N$
        Compute policy gradient $\nabla_\phi(\tau_i)$ for $i \in I_{\text{inv}}$
         $\phi \leftarrow \phi + \eta_\pi \cdot \frac{1}{|I_{\text{inv}}|} \sum_{i \in I_{\text{inv}}} \nabla_\phi(\tau_i)$
         $\theta' \leftarrow \zeta \theta + (1 - \zeta)\theta', \quad \phi' \leftarrow \zeta \phi + (1 - \zeta)\phi'$
    end for
end for
Default hyperparameters: $\alpha = 0.4$ , $\beta = 0.4$ , $\lambda = 0.5$ , $\zeta = 0.005$ , $\eta_\pi = \eta_Q = 3 \times 10^{-4}$ , mini-batch size $N = 256$ , replay buffer capacity matching total training steps ( $10^6$ or $2 \times 10^6$ steps).
Knowl 3 — Inverse Prioritized Sampling Scheme for Actor Policy Updates
model/method
To train the actor network on experiences where the critic has low uncertainty (minimal temporal-difference error), an inverse sampling distribution is derived over the prioritized replay buffer.

Transitions are stored in a binary sum-tree data structure where leaf nodes store priority values $p(\tau_i)$ clipped to at least 1 using the Loss-Adjusted Prioritized (LAP) formulation: $p(\tau_i) = \frac{\max(|\delta_\theta(\tau_i)|^\alpha, 1)}{\sum_j \max(|\delta_\theta(\tau_j)|^\alpha, 1)}$ , with prioritization exponent $\alpha = 0.4$ . The probability distribution $\tilde{p}(\tau_i)$ for sampling transitions to update the actor network is defined as inversely proportional to $p(\tau_i)$ : $\tilde{p}(\tau_i) = \frac{p_{\max}}{p(\tau_i)} = \max_k \left( \frac{\max(|\delta_\theta(\tau_k)|^\alpha, 1)}{\sum_j \max(|\delta_\theta(\tau_j)|^\alpha, 1)} \right) \cdot \frac{\sum_j \max(|\delta_\theta(\tau_j)|^\alpha, 1)}{\max(|\delta_\theta(\tau_i)|^\alpha, 1)}$ where $p_{\max}$ is the maximum priority currently stored in the replay buffer. Clipping priorities at 1 eliminates dead transitions without requiring an additive constant $\mu$ , ensures that the global inverse operation is strictly non-zero and numerically well-defined, and preserves the relative proportions of proportional prioritization.
Knowl 4 — Shared Uniform Mini-Batch Sampling for Actor-Critic Stability
model/method
In actor-critic theory, critic parameters and actor parameters are interdependent because the policy determines the visited state-action distribution and the critic evaluates the actions selected by the actor. If the actor is trained exclusively on low TD error transitions via inverse sampling and the critic is trained exclusively on large TD error transitions via prioritized sampling, their update distributions can diverge completely, destabilizing learning.

To ensure stability and preserve parameter coupling, each training step allocates a fraction $\lambda \in [0, 1]$ of the total mini-batch size $N$ to be sampled uniformly at random from the experience replay buffer $R$ . Both the actor and critic networks are optimized on this identical mini-batch of size $\lambda \cdot N$ . The remaining $(1 - \lambda) \cdot N$ transitions are sampled separately via prioritized sampling for the critic and inverse prioritized sampling for the actor. A value of $\lambda = 0.5$ provides the optimal empirical trade-off between actor-critic coupling and prioritized learning across continuous control benchmarks.
Knowl 5 — Prioritized Approximate Loss Function for Uniform Critic Updates
equation
When a mini-batch of transitions $I$ with size $|I| = \lambda \cdot N$ is sampled uniformly from the replay buffer, the critic network $Q_\theta$ is updated using the Prioritized Approximate Loss (PAL) function rather than standard mean-squared error (MSE). The PAL function provides the same expected gradient under uniform sampling as the Huber loss (with threshold $\kappa = 1$ ) under prioritized sampling, preventing outlier bias leakage: $\xi = \frac{\sum_{j \in I} \max(|\delta_\theta(\tau_j)|^\alpha, 1)}{|I|}$ $L_{\text{PAL}}(\delta_\theta(\tau_i)) = \frac{1}{\xi} \begin{cases} 0.5 \delta_\theta(\tau_i)^2 & \text{if } |\delta_\theta(\tau_i)| \le 1 \\ \frac{|\delta_\theta(\tau_i)|^{1+\alpha}}{1+\alpha} & \text{otherwise} \end{cases}$ where $\delta_\theta(\tau_i) = r_i + \gamma Q_{\theta'}(s_{i+1}, a_{i+1}) - Q_\theta(s_i, a_i)$ is the temporal-difference error, and $\alpha = 0.4$ is the prioritization exponent. The normalization factor $\xi$ scales the loss according to the average clipped priority in the uniform mini-batch.

Knowl 6 — Empirical Performance of LA3P on Continuous Control Benchmarks

data/table

LA3P combined with Soft Actor-Critic (SAC) and Twin Delayed Deep Deterministic Policy Gradient (TD3) was evaluated against Prioritized Experience Replay (PER), Loss Adjusted Prioritized Experience Replay (LAP), Model-Augmented PER (MaPER), and uniform sampling across continuous control tasks in MuJoCo and Box2D. Evaluations were conducted every 1000 steps over 10 random seeds; table values show the average evaluation return across the final 10 evaluation points (with 95% confidence intervals).

Method	Ant	BipedalWalker	HalfCheetah	Hopper	Humanoid	LunarLanderContinuous	Swimmer	Walker2d
SAC + LA3P	4976.28 $\pm$ 827.81	318.91 $\pm$ 23.13	12101.70 $\pm$ 315.74	3917.77 $\pm$ 461.58	5491.76 $\pm$ 189.21	269.06 $\pm$ 9.48	104.88 $\pm$ 21.33	5449.14 $\pm$ 265.77
SAC + LAP	3130.02 $\pm$ 950.52	320.05 $\pm$ 11.12	10741.91 $\pm$ 1048.96	2324.29 $\pm$ 326.32	4927.61 $\pm$ 474.05	272.66 $\pm$ 7.62	75.77 $\pm$ 19.27	4403.11 $\pm$ 386.07
SAC + MaPER	3923.47 $\pm$ 369.85	308.03 $\pm$ 13.68	8687.17 $\pm$ 344.27	2840.91 $\pm$ 195.49	5017.23 $\pm$ 151.31	265.22 $\pm$ 17.56	74.64 $\pm$ 7.00	4243.83 $\pm$ 185.00
SAC + PER	3842.51 $\pm$ 628.74	304.85 $\pm$ 5.76	4861.91 $\pm$ 260.46	1999.58 $\pm$ 339.68	4643.74 $\pm$ 404.31	244.62 $\pm$ 59.53	49.94 $\pm$ 1.85	3417.08 $\pm$ 243.83
SAC	3906.49 $\pm$ 628.06	290.44 $\pm$ 49.18	7196.27 $\pm$ 722.02	3025.97 $\pm$ 332.20	4774.19 $\pm$ 314.03	281.61 $\pm$ 3.26	51.21 $\pm$ 1.74	3609.33 $\pm$ 454.04
TD3 + LA3P	5536.67 $\pm$ 210.97	321.17 $\pm$ 4.11	11567.61 $\pm$ 833.67	3563.00 $\pm$ 211.70	5282.96 $\pm$ 224.54	276.60 $\pm$ 8.51	104.98 $\pm$ 23.62	4776.68 $\pm$ 339.80
TD3 + LAP	4806.97 $\pm$ 708.24	293.68 $\pm$ 41.43	10343.27 $\pm$ 1081.79	3145.94 $\pm$ 416.89	5201.14 $\pm$ 176.24	274.22 $\pm$ 6.72	75.10 $\pm$ 22.19	3700.36 $\pm$ 685.96
TD3 + MaPER	4364.80 $\pm$ 209.22	306.43 $\pm$ 24.74	9241.38 $\pm$ 620.15	3027.40 $\pm$ 228.69	5087.84 $\pm$ 124.66	267.60 $\pm$ 7.46	65.13 $\pm$ 7.84	3410.70 $\pm$ 325.05
TD3 + PER	4269.16 $\pm$ 536.38	244.55 $\pm$ 75.49	5242.75 $\pm$ 371.66	2577.20 $\pm$ 339.48	5050.35 $\pm$ 164.63	251.96 $\pm$ 25.94	53.61 $\pm$ 3.57	3031.57 $\pm$ 826.06
TD3	4243.79 $\pm$ 582.32	277.14 $\pm$ 74.55	8064.88 $\pm$ 1134.70	2857.00 $\pm$ 512.74	4964.12 $\pm$ 224.71	274.95 $\pm$ 4.20	50.80 $\pm$ 1.06	3312.46 $\pm$ 822.78

Ant, HalfCheetah, Humanoid, and Swimmer were run for $2 \times 10^6$ steps; other tasks ran for $10^6$ steps. Pairwise 2-sample t-tests against all competing methods confirmed statistically significant improvements ( $p < 0.05$ ) by LA3P on almost all benchmarks, with the largest gains observed on long-horizon environments such as HalfCheetah and Swimmer.

Knowl 7 — Ablation Analysis of LA3P Components and Uniform Sampling Fraction

data/table

An ablation study on LA3P using TD3 over 10 trials ( $10^6$ steps each, reporting the average of the last 10 evaluation points $\pm$ 95% confidence intervals) investigated the individual contributions of LAP loss correction, PAL loss correction, uniform shared sampling, low TD error shared transitions, and varying uniform sampling fractions $\lambda \in \{0.1, 0.3, 0.5, 0.7, 0.9\}$ .

Setting	Ant	HalfCheetah	Humanoid	Walker2d
LA3P (complete)	5197.46 $\pm$ 162.04	11225.14 $\pm$ 800.59	5131.11 $\pm$ 193.26	4776.68 $\pm$ 339.80
Low TD-error	3485.06 $\pm$ 834.26	10992.05 $\pm$ 467.13	3938.13 $\pm$ 1395.00	4438.29 $\pm$ 320.47
w/o LAP	3408.55 $\pm$ 569.04	4580.27 $\pm$ 250.82	3585.06 $\pm$ 830.28	3262.49 $\pm$ 252.69
w/o PAL	3975.29 $\pm$ 1130.62	7560.50 $\pm$ 762.22	4879.43 $\pm$ 187.23	4543.92 $\pm$ 398.97
w/o Uniform Sampling	4431.87 $\pm$ 716.48	10483.11 $\pm$ 594.31	5058.69 $\pm$ 111.42	4254.55 $\pm$ 387.41
$\lambda = 0.1$	3768.74 $\pm$ 1007.13	11203.83 $\pm$ 550.87	4695.52 $\pm$ 99.62	4562.77 $\pm$ 372.07
$\lambda = 0.3$	4903.34 $\pm$ 385.48	10460.52 $\pm$ 933.14	4528.28 $\pm$ 1113.55	4425.08 $\pm$ 324.29
$\lambda = 0.5$	5197.46 $\pm$ 162.04	11225.14 $\pm$ 800.59	5131.11 $\pm$ 193.26	4776.68 $\pm$ 339.80
$\lambda = 0.7$	4383.97 $\pm$ 828.71	10656.92 $\pm$ 735.91	4874.50 $\pm$ 130.33	4253.76 $\pm$ 829.14
$\lambda = 0.9$	3882.08 $\pm$ 936.85	10547.85 $\pm$ 871.63	3757.90 $\pm$ 1344.11	4545.97 $\pm$ 567.28

The ablation indicates that removing LAP causes the most severe performance degradation (e.g., dropping HalfCheetah from 11225.14 to 4580.27). Omitting the shared uniform mini-batch or substituting it with low TD error transitions also degrades performance due to reduced sampling diversity. Across fraction values, $\lambda = 0.5$ consistently yields the highest returns.

Knowl 8 — Worst-Case Time Complexity and SIMD Parallelization of LA3P
theoretical result
The theoretical per-step time complexity of vanilla Prioritized Experience Replay (PER) using a binary sum-tree is $\mathcal{O}(\log |R|)$ , where $|R|$ is the replay buffer capacity. In the LA3P framework, computing the inverse priority array $\tilde{p}(\tau_i) = p_{\max} / p(\tau_i)$ across the entire sum-tree requires an element-wise division over the buffer, which incurs an $\mathcal{O}(|R|)$ operation. Consequently, the total per-step theoretical worst-case time complexity of LA3P is: $\mathcal{O}(\log |R|) + \mathcal{O}(|R|) = \mathcal{O}(|R|)$

In practical hardware execution, modern CPUs implement Single Instruction, Multiple Data (SIMD) instruction sets that execute array inversions in parallel across CPU cores. Because all clipped priorities satisfy $p(\tau_i) \ge 1$ , division-by-zero is avoided and the array operation is strictly regular. Across empirical benchmarks, doubling the replay buffer size $|R|$ from $10^6$ to $2 \times 10^6$ increased the total wall-clock runtime of LA3P by only $186.96\%$ on SAC (from $459.18 \pm 1.47$ mins to $858.50 \pm 1.50$ mins) and $183.47\%$ on TD3 (from $238.29 \pm 2.13$ mins to $437.18 \pm 2.08$ mins), demonstrating sub-linear practical overhead.

Coverage note — None omitted; all primary theoretical foundations, algorithmic components, equations, empirical benchmarks, ablation studies, and complexity analyses contributed by the paper are fully covered.

References

1.Andre, D., Friedman, N., & Parr, R. (1997). Generalized prioritized sweeping. In Jordan, M., Kearns, M., & Solla, S. (Eds.), Advances in Neural Information Processing Systems, Vol. 10. MIT Press.
2.Barth-Maron, G., Hoffman, M. W., Budden, D., Dabney, W., Horgan, D., TB, D., Muldal, A., Heess, N., & Lillicrap, T. (2018). Distributional policy gradients. In International Conference on Learning Representations.
3.Bellemare, M. G., Naddaf, Y., Veness, J., & Bowling, M. (2013). The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47, 253–279.
4.Bellman, R. E. (2003). Dynamic Programming. Dover Publications, Inc., USA.
5.Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., & Zaremba, W. (2016). Openai gym. CoRR, abs/1606.01540.
6.Fujimoto, S., Meger, D., & Precup, D. (2020). An equivalence between loss functions and non-uniform sampling in experience replay. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., & Lin, H. (Eds.), Advances in Neural Information Processing Systems, Vol. 33, pp. 14219–14230. Curran Associates, Inc.
7.Fujimoto, S., van Hoof, H., & Meger, D. (2018). Addressing function approximation error in actor-critic methods. In Dy, J., & Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, pp. 1587–1596, Stockholmsmässan, Stockholm SWEDEN. PMLR.
8.Gruslys, A., Dabney, W., Azar, M. G., Piot, B., Bellemare, M., & Munos, R. (2018). The reactor: A fast and sample-efficient actor-critic agent for reinforcement learning. In International Conference on Learning Representations.
9.Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018a). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Dy, J., & Krause, A. (Eds.), Proceedings of the 35th International Conference on Machine Learning, Vol. 80 of Proceedings of Machine Learning Research, pp. 1861–1870. PMLR.
10.Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., Kumar, V., Zhu, H., Gupta, A., Abbeel, P., & Levine, S. (2018b). Soft actor-critic algorithms and applications..
11.Henderson, P., Islam, R., Bachman, P., Pineau, J., Precup, D., & Meger, D. (2018). Deep reinforcement learning that matters. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’18/IAAI’18/EAAI’18, New Orleans, Louisiana, USA. AAAI Press.
12.Hessel, M., Modayil, J., van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M., & Silver, D. (2018). Rainbow: Combining improvements in deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1).
13.Hester, T., Vecerik, M., Pietquin, O., Lanctot, M., Schaul, T., Piot, B., Horgan, D., Quan, J., Sendonaris, A., Osband, I., Dulac-Arnold, G., Agapiou, J., Leibo, J., & Gruslys, A. (2018). Deep q-learning from demonstrations. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1).
14.Horgan, D., Quan, J., Budden, D., Barth-Maron, G., Hessel, M., van Hasselt, H., & Silver, D. (2018). Distributed prioritized experience replay. In International Conference on Learning Representations.
15.Isele, D., & Cosgun, A. (2018). Selective experience replay for lifelong learning. Proceedings of the AAAI Conference on Artificial Intelligence, 32 (1).
16.ji Lin, L. (1992). Self-improving reactive agents based on reinforcement learning, planning and teaching. In Machine Learning, pp. 293–321.
17.Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). Reinforcement learning: A survey. Journal of Artificial Intelligence Research, 4, 237–285.
18.Kingma, D. P., & Ba, J. (2015). Adam: A method for stochastic optimization. In ICLR (Poster).
19.Konda, V., & Tsitsiklis, J. (1999). Actor-critic algorithms. In Solla, S., Leen, T., & Müller, K. (Eds.), Advances in Neural Information Processing Systems, Vol. 12. MIT Press.
20.Lazaridis, A., Fachantidis, A., & Vlahavas, I. (2020). Deep reinforcement learning: A state-of-the-art walkthrough. Journal of Artificial Intelligence Research, 69, 1421–1471.
21.Liu, R., & Zou, J. (2018). The effects of memory replay in reinforcement learning. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 478–485.
22.Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., & Hassabis, D. (2015). Human-level control through deep reinforcement learning. Nature, 518 (7540), 529–533.
23.Moore, A. W., & Atkeson, C. G. (1993). Prioritized sweeping: Reinforcement learning with less data and less time. Machine Learning, 13 (1), 103–130.
24.Novati, G., & Koumoutsakos, P. (2019). Remember and forget for experience replay. In Chaudhuri, K., & Salakhutdinov, R. (Eds.), Proceedings of the 36th International Conference on Machine Learning, Vol. 97 of Proceedings of Machine Learning Research, pp. 4851–4860. PMLR.
25.Oh, Y., Lee, K., Shin, J., Yang, E., & Hwang, S. J. (2021). Learning to sample with local and global contexts in experience replay buffer. In International Conference on Learning Representations.
26.Oh, Y., Shin, J., Yang, E., & Hwang, S. J. (2022). Model-augmented prioritized experience replay. In International Conference on Learning Representations.
27.Parberry, I. (2013). Introduction to Game Physics with Box2D (1st edition). CRC Press, Inc., USA.
28.Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2015). Prioritized experience replay.. cite arxiv:1511.05952Comment: Published at ICLR 2016.
29.Schlegel, M., Chung, W., Graves, D., Qian, J., & White, M. (2019). Importance Resampling for Off-Policy Prediction. Curran Associates Inc., Red Hook, NY, USA.
30.Sutton, R. (1988). Learning to predict by the method of temporal differences. Machine Learning, 3, 9–44.
31.Sutton, R., Mcallester, D., Singh, S., & Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. Adv. Neural Inf. Process. Syst, 12.
32.Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.
33.Todorov, E., Erez, T., & Tassa, Y. (2012). Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026–5033.
34.Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8 (3), 279–292.
35.Williams, R. J. (1992). Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn., 8 (3–4), 229–256.
36.Zha, D., Lai, K.-H., Zhou, K., & Hu, X. (2019). Experience replay optimization. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 4243–4249. International Joint Conferences on Artificial Intelligence Organization.

Citation

MLA

Saglam, B., et al. “Actor Prioritized Experience Replay”. arXiv, 2022, http://arxiv.org/abs/2209.00532v1.

APA

Saglam, B., Mutlu, F. B., Cicek, D. C., & Kozat, S. S. (2022). Actor Prioritized Experience Replay. arXiv. http://arxiv.org/abs/2209.00532v1

Chicago

Saglam, B., F. B. Mutlu, D. C. Cicek, and S. S. Kozat. 2022. “Actor Prioritized Experience Replay”. arXiv. http://arxiv.org/abs/2209.00532v1.

Harvard

Saglam, B. et al. (2022) “Actor Prioritized Experience Replay”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2209.00532v1.

Vancouver

1. Saglam B, Mutlu FB, Cicek DC, Kozat SS (2022) Actor Prioritized Experience Replay. arXiv

BibTeX

@article{saglam2022actor,
  title = {Actor Prioritized Experience Replay},
  author = {Saglam, Baturay and Mutlu, Furkan B. and Cicek, Dogan C. and Kozat, Suleyman S.},
  year = {2022},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2209.00532v1},
  eprint = {2209.00532}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Actor Prioritized Experience Replay

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — Policy Gradient Divergence Under High TD Error Transitions

Knowl 2 — Loss-Adjusted Approximate Actor Prioritized Experience Replay Algorithm

Knowl 3 — Inverse Prioritized Sampling Scheme for Actor Policy Updates

Knowl 4 — Shared Uniform Mini-Batch Sampling for Actor-Critic Stability