• TD learning's error accumulates through Bellman bootstrapping over the whole horizon; n-step TD only cuts the number of recursions by a constant factor n and forces a variance tradeoff, while divide-and-conquer cuts recursions logarithmically instead of linearly.
• The divide-and-conquer update exploits the triangle inequality on shortest-path distance between states: a value can be updated from two smaller values via an optimal subgoal midpoint, rather than one-step bootstrapping.
• Since finding the true optimal subgoal is intractable in continuous spaces, the method restricts the search to states already lying between the start and goal in a sampled dataset trajectory, and replaces the max operator with expectile regression to avoid value overestimation.
• On OGBench's hardest humanoidmaze and puzzle tasks (1B-sized datasets, up to 3,000 environment steps), the method matched the best individually-tuned n-step TD baseline on every task without needing to tune n, beating TD, Monte Carlo, and quasimetric-learning baselines.

It offers an alternative to TD learning's scalability ceiling for off-policy RL, relevant to anyone training agents on expensive-to-collect long-horizon data like robotics or dialogue.

• articlePolicy Gradient AlgorithmsLilian Weng
• articleGSPO: Towards Scalable Reinforcement Learning for Language ModelsQwen Team
• articleRL Systems: Mind the Gap — Matching Trainer and Generator ThroughputKimbo Chen

Checking sign-in…

Loading comments…