Solving Sokoban using Hierarchical Reinforcement Learning with Landmarks

• URL: http://arxiv.org/abs/2504.04366v1
• Date: Sun, 06 Apr 2025 05:30:21 GMT
• Title: Solving Sokoban using Hierarchical Reinforcement Learning with Landmarks
• Authors: Sergey Pastukhov,
• Abstract summary: We introduce a novel hierarchical reinforcement learning framework, successfully applied to the puzzle game Sokoban.<n>Our approach constructs a six-level policy hierarchy, where each higher-level policy generates subgoals for the level below.<n>All subgoals and policies are learned end-to-end from scratch, without any domain knowledge.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a novel hierarchical reinforcement learning (HRL) framework that performs top-down recursive planning via learned subgoals, successfully applied to the complex combinatorial puzzle game Sokoban. Our approach constructs a six-level policy hierarchy, where each higher-level policy generates subgoals for the level below. All subgoals and policies are learned end-to-end from scratch, without any domain knowledge. Our results show that the agent can generate long action sequences from a single high-level call. While prior work has explored 2-3 level hierarchies and subgoal-based planning heuristics, we demonstrate that deep recursive goal decomposition can emerge purely from learning, and that such hierarchies can scale effectively to hard puzzle domains.

Related papers

• On the benefits of pixel-based hierarchical policies for task generalization [7.207480346660617]
  Reinforcement learning practitioners often avoid hierarchical policies, especially in image-based observation spaces. We analyze the benefits of hierarchy through simulated multi-task robotic control experiments from pixels.
  arXiv  Detail & Related papers  (2024-07-27T01:26:26Z)
• Reinforcement Learning with Options and State Representation [105.82346211739433]
  This thesis aims to explore the reinforcement learning field and build on existing methods to produce improved ones. It addresses such goals by decomposing learning tasks in a hierarchical fashion known as Hierarchical Reinforcement Learning.
  arXiv  Detail & Related papers  (2024-03-16T08:30:55Z)
• Feudal Graph Reinforcement Learning [18.069747511100132]
  Graph-based representations and message-passing modular policies constitute prominent approaches to tackling composable control problems in reinforcement learning (RL)<n>We propose a novel methodology, named Feudal Graph Reinforcement Learning (FGRL), that addresses such challenges by relying on hierarchical RL and a pyramidal message-passing architecture.<n>In particular, FGRL defines a hierarchy of policies where high-level commands are propagated from the top of the hierarchy down through a layered graph structure.
  arXiv  Detail & Related papers  (2023-04-11T09:51:13Z)
• Hierarchical Imitation Learning with Vector Quantized Models [77.67190661002691]
  We propose to use reinforcement learning to identify subgoals in expert trajectories. We build a vector-quantized generative model for the identified subgoals to perform subgoal-level planning. In experiments, the algorithm excels at solving complex, long-horizon decision-making problems outperforming state-of-the-art.
  arXiv  Detail & Related papers  (2023-01-30T15:04:39Z)
• Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Control [44.77500987121531]
  Hierarchical Imitation Learning (HIL) has been proposed to recover highly-complex behaviors in long-horizon tasks from expert demonstrations. We develop a novel HIL algorithm based on Adversarial Inverse Reinforcement Learning. We also propose a Variational Autoencoder framework for learning with our objectives in an end-to-end fashion.
  arXiv  Detail & Related papers  (2022-10-05T00:28:26Z)
• Planning to Practice: Efficient Online Fine-Tuning by Composing Goals in Latent Space [76.46113138484947]
  General-purpose robots require diverse repertoires of behaviors to complete challenging tasks in real-world unstructured environments. To address this issue, goal-conditioned reinforcement learning aims to acquire policies that can reach goals for a wide range of tasks on command. We propose Planning to Practice, a method that makes it practical to train goal-conditioned policies for long-horizon tasks.
  arXiv  Detail & Related papers  (2022-05-17T06:58:17Z)
• On Credit Assignment in Hierarchical Reinforcement Learning [0.0]
  Hierarchical Reinforcement Learning (HRL) has held longstanding promise to advance reinforcement learning. We show how e.g., a 1-step hierarchical backup' can be seen as a conventional multistep backup with $n$ skip connections over time. We develop a new hierarchical algorithm Hier$Q_k(lambda)$, for which we demonstrate that hierarchical credit assignment alone can already boost agent performance.
  arXiv  Detail & Related papers  (2022-03-07T11:13:09Z)
• Provable Hierarchy-Based Meta-Reinforcement Learning [50.17896588738377]
  We analyze HRL in the meta-RL setting, where learner learns latent hierarchical structure during meta-training for use in a downstream task. We provide "diversity conditions" which, together with a tractable optimism-based algorithm, guarantee sample-efficient recovery of this natural hierarchy. Our bounds incorporate common notions in HRL literature such as temporal and state/action abstractions, suggesting that our setting and analysis capture important features of HRL in practice.
  arXiv  Detail & Related papers  (2021-10-18T17:56:02Z)
• Learning Task Decomposition with Ordered Memory Policy Network [73.3813423684999]
  We propose Ordered Memory Policy Network (OMPN) to discover subtask hierarchy by learning from demonstration. OMPN can be applied to partially observable environments and still achieve higher task decomposition performance. Our visualization confirms that the subtask hierarchy can emerge in our model.
  arXiv  Detail & Related papers  (2021-03-19T18:13:35Z)
• Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning [78.65083326918351]
  We consider alternatives to an implicit sequential planning assumption. We propose Divide-and-Conquer Monte Carlo Tree Search (DC-MCTS) for approximating the optimal plan. We show that this algorithmic flexibility over planning order leads to improved results in navigation tasks in grid-worlds.
  arXiv  Detail & Related papers  (2020-04-23T18:08:58Z)
• Learning Functionally Decomposed Hierarchies for Continuous Control Tasks with Path Planning [36.050432925402845]
  We present HiDe, a novel hierarchical reinforcement learning architecture that successfully solves long horizon control tasks. We experimentally show that our method generalizes across unseen test environments and can scale to 3x horizon length compared to both learning and non-learning based methods.
  arXiv  Detail & Related papers  (2020-02-14T10:19:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.