Research map / Reinforcement learning / MDPs and planning
A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| symbolic SAT encoding instead of explicit belief-support MDP construction | almost-sure reachability in POMDPs · Hallway HW1 | runtime (s): 128.9 -> 0.6 | Helped |
| symbolic SAT encoding instead of explicit algorithm | almost-sure reachability · Escape9 | runtime (s): 688.6 -> 60.2 | Helped |
| symbolic SAT encoding instead of explicit algorithm | almost-sure reachability · RockSample RS[9] | runtime (s): 197.3 -> 79.1 | Helped |
| symbolic SAT encoding instead of explicit algorithm | almost-sure reachability · Escape3 | runtime (s): 0.4 -> 0.2 | Mixed |
| increase memory states from 1 to 2 in Hallway (memoryless to small memory) (ablation) | SAT encoding · Hallway HW1 | existence of winning strategy | Helped |
| increase memory states from 1 to 2 (larger SAT instance) (ablation) | SAT encoding · Hallway HW8 | runtime (s): 55.4 -> 1157.1 | Hurt |
Closest papers by meaning
- Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.88)
- Online POMDP Planning with Anytime Deterministic Guarantees (NeurIPS 2023 · similarity 0.88)
- Belief-State Query Policies for User-Aligned POMDPs (NeurIPS 2024 · similarity 0.87)
- Point-Based Methods for Model Checking in Partially Observable Markov Decision Processes (AAAI 2020 · similarity 0.87)
- Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach (AAAI 2025 · similarity 0.87)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.