RL without TD learning
This Berkeley BAIR blog post introduces a reinforcement learning approach based on a divide-and-conquer paradigm rather than temporal difference (TD) learning. The author argues that TD learning struggles to scale to long-horizon tasks because errors in bootstrapped value estimates accumulate across the horizon. The proposed divide-and-conquer method splits a trajectory into two equal halves and combines their values, which in theory reduces the number of Bellman recursions logarithmically rather than linearly, offering a path toward scalable off-policy RL.
Key Takeaways
- In this post, I'll introduce a reinforcement learning (RL) algorithm based on an "alternative" paradigm: divide and conquer .
Unlike traditional methods, this algorithm is not based on temporal difference (TD) learning (which has scalability challenges ), and scales well to long-horizon tasks.
- In other words, we have to throw away old data each time we update the policy.
Algorithms like PPO and GRPO (and policy gradient methods in general) belong to this category.
- However, we still haven't found a "scalable" off-policy RL algorithm that scales well to complex, long-horizon tasks.
This is basically what makes TD learning struggle to scale to long-horizon tasks (see this post if you're interested in more details).
- While this is a reasonable solution (and often works well ), it is highly unsatisfactory.
First, it doesn't fundamentally solve the error accumulation problem; it only reduces the number of Bellman recursions by a constant factor ($n$).
- This way, we can (in theory) reduce the number of Bellman recursions logarithmically (not linearly!).
In this post, I'll introduce a reinforcement learning (RL) algorithm based on an "alternative" paradigm: divide and conquer . Unlike traditional methods, this algorithm is not based on temporal difference (TD) learning (which has scalability challenges ), and scales well to long-horizon tasks. We can do Reinforcement Learning (RL) based on divide and conquer, instead of temporal difference (TD) learning.
Problem setting: off-policy RL Our problem setting is off-policy RL . Let's briefly review what this means. There are two classes of algorithms in RL: on-policy RL and off-policy RL.
On-policy RL means we can only use fresh data collected by the current policy. In other words, we have to throw away old data each time we update the policy. Algorithms like PPO and GRPO (and policy gradient methods in general) belong to this category.
For more details please read the original article at Berkeley BAIR.
Continue Learning
Comments
Comments appear only after moderation. Your email identifies your submission to the moderator and is never displayed here.
No approved comments yet.