<p>When I run Soft-Actor-Critic (off-policy) in my Environment, the calculation of gradient updates takes almost twice the time compared to using PPO (on-policy).
I also saw that ACER has a higher time complexity compared to PPO in this paper <a href="https://arxiv.org/pdf/2112.03798.pdf" rel="nofollow noreferrer">PPO with Prioritized Trajectory Replay</a></p>
<p>In their comparison, ACER took almost 5 times longer (wall-clock time) compared to PPO for 1000 steps in Altantis-v0 benchmark.</p>
<p>That's why it came to my mind that this maybe has to do with their different algorithmic approaches (off- vs. on-policy).</p>
<p>This question is not about the difference between sample- and computational- or time efficiency, as this was quite well explained <a href="https://ai.stackexchange.com/q/35182/2444">here</a>.</p>
<p>The question is: Is my assumption correct that off-policy algorithms are more computationally or time complex than on-policy ones? If so, why? Is there a certain component like the replay buffer which increases complexity?</p>
<p>Or is my assumption incorrect and the computational or time complexity differences between the algorithms was only implementation related, meaning that off-policy algorithms doesn't necessarily have to be more computational complex or take more time than on-policy ones?</p>

CC BY-SA 4.0
2022-05-02T14:44:44.587Z
I think your question in the body of the post is partially a duplicate of [this](https://ai.stackexchange.com/q/35182/2444). The questions are not exactly the same, but my answer there should give you some insight on why more sample efficient algorithms might require more computational resources. By the way, you're asking here 2 distinct questions (the one in the title and the other one) - I recommend that you clarify what your main question is.
nbro
CC BY-SA 4.0
2022-05-03T18:12:18.960Z
@nbro Thanks for your reply. I indeed read that question and it addresses the topic sample vs computational efficiency in that it gives examples of algorithms that fall more or less in some category compared to others. However, my question is why is this the case: Like why is it that e.g. SAC has a higher computational complexity compared to PPO? Is it because the sampling of a replay buffer? Or was this just some coincidence and is not linked to algo categories off-/on-policy? I will adapt my question to make my question more clear in this regard.
kitaird
CC BY-SA 4.0
2022-05-04T04:20:56.530Z
1. I don't see where that paper you link talks about computational complexity. Wall time is not the same as computational complexity.
Taw
CC BY-SA 4.0
2022-05-04T04:21:11.687Z
2. PPO is off policy.
Taw
CC BY-SA 4.0
2022-05-04T09:00:10.797Z
@Taw True, wall time is not the same as computational complexity. I will change my question to ask about time complexity. But PPO is an on-policy algorithm.
kitaird
CC BY-SA 4.0
2022-05-04T09:46:17.603Z
@Taw PPO is on-policy, as far as I am aware. It uses trajectories generated by the current policy to make updates to the policy parameters.
David
CC BY-SA 4.0
2022-05-04T09:48:52.177Z
@kitaird off-policy algorithms will generally have higher computational complexity than on-policy algorithms simply because you are doing more gradient updates (in general) than on-policy algorithms. Consider the SAC algorithm: at each step of an episode we sample a batch from our replay buffer and make a gradient update. If the batch size is large, then this computational overhead will be large. Compare this to PPO where we only make updates every $T$, it makes sense that the overhead would be less.
David
CC BY-SA 4.0
2022-05-04T09:51:57.000Z
It is technically off-policy because the current policy may be slightly different than the policy used to generate the trajectories. But maybe it was too pedantic to bring that up.
Taw
CC BY-SA 4.0
2022-05-04T09:52:32.640Z
@kitaird Its difficult to compare wall times of algorithms because they may use different network architectures. It's not clear to me that the paper you linked (which does not appear to be published) accounts for that.
Taw
CC BY-SA 4.0
2022-05-04T10:02:33.490Z
@Taw I see what you're getting at; I think you could argue for it being a hybrid of both on and off policy, but I would say that because the trust region constraint the updated policy to not stray too far from the original policy that generated the rollouts then it is still considered on-policy.
David
<reinforcement-learning><off-policy-methods><on-policy-methods><computational-complexity><sample-efficiency>
Why do off-policy algorithms suffer from worse computational or time efficiency compared to on-policy algorithms?
kitaird
# Why do off-policy algorithms suffer from worse computational or time efficiency compared to on-policy algorithms?

(Asked by: username_0 on 2022-05-02)

When I run Soft-Actor-Critic (off-policy) in my Environment, the calculation of gradient updates takes almost twice the time compared to using PPO (on-policy).
I also saw that ACER has a higher time complexity compared to PPO in this paper [PPO with Prioritized Trajectory Replay](https://arxiv.org/pdf/2112.03798.pdf)

In their comparison, ACER took almost 5 times longer (wall-clock time) compared to PPO for 1000 steps in Altantis-v0 benchmark.

That's why it came to my mind that this maybe has to do with their different algorithmic approaches (off- vs. on-policy).

This question is not about the difference between sample- and computational- or time efficiency, as this was quite well explained [here](https://ai.stackexchange.com/q/35182/2444).

The question is: Is my assumption correct that off-policy algorithms are more computationally or time complex than on-policy ones? If so, why? Is there a certain component like the replay buffer which increases complexity?

Or is my assumption incorrect and the computational or time complexity differences between the algorithms was only implementation related, meaning that off-policy algorithms doesn't necessarily have to be more computational complex or take more time than on-policy ones?

**Tags:** reinforcement-learning, off-policy-methods, on-policy-methods, computational-complexity, sample-efficiency

> **Comments:**
> **username_1**: I think your question in the body of the post is partially a duplicate of [this](https://ai.stackexchange.com/q/35182/2444). The questions are not exactly the same, but my answer there should give you some insight on why more sample efficient algorithms might require more computational resources. By the way, you're asking here 2 distinct questions (the one in the title and the other one) - I recommend that you clarify what your main question is.  
> **username_0**: @username_1 Thanks for your reply. I indeed read that question and it addresses the topic sample vs computational efficiency in that it gives examples of algorithms that fall more or less in some category compared to others. However, my question is why is this the case: Like why is it that e.g. SAC has a higher computational complexity compared to PPO? Is it because the sampling of a replay buffer? Or was this just some coincidence and is not linked to algo categories off-/on-policy? I will adapt my question to make my question more clear in this regard.  
> **username_2**: 1. I don't see where that paper you link talks about computational complexity. Wall time is not the same as computational complexity.  
> **username_2**: 2. PPO is off policy.  
> **username_0**: @username_2 True, wall time is not the same as computational complexity. I will change my question to ask about time complexity. But PPO is an on-policy algorithm.  
> **username_3**: @username_2 PPO is on-policy, as far as I am aware. It uses trajectories generated by the current policy to make updates to the policy parameters.  
> **username_3**: @username_0 off-policy algorithms will generally have higher computational complexity than on-policy algorithms simply because you are doing more gradient updates (in general) than on-policy algorithms. Consider the SAC algorithm: at each step of an episode we sample a batch from our replay buffer and make a gradient update. If the batch size is large, then this computational overhead will be large. Compare this to PPO where we only make updates every $T$, it makes sense that the overhead would be less.  
> **username_2**: It is technically off-policy because the current policy may be slightly different than the policy used to generate the trajectories. But maybe it was too pedantic to bring that up.  
> **username_2**: @username_0 Its difficult to compare wall times of algorithms because they may use different network architectures. It's not clear to me that the paper you linked (which does not appear to be published) accounts for that.  
> **username_3**: @username_2 I see what you're getting at; I think you could argue for it being a hybrid of both on and off policy, but I would say that because the trust region constraint the updated policy to not stray too far from the original policy that generated the rollouts then it is still considered on-policy.  

---

## 0 answers

