Quasipolynomial Approximate Planning for Decodable POMDPs
Original title: Quasipolynomial-Time Planning for Decodable POMDPs
Introduces quasipolynomial-time approximate planning algorithms for ρ-decodable POMDPs, which are weaker than observability assumptions.
Authors study planning for finite-horizon POMDPs. Provide quasipolynomial-time algorithms for ρ-decodable POMDPs where decodability constant computable in poly time. Show decodability implies ℓ1- and ℓ2-observability but is strictly weaker. Optimal constant computable in polynomial time unlike ℓ1-observability which is NP-hard.
- Quasipolynomial-time approximate planning for ρ-decodable POMDPs
- Decodability strictly weaker than ℓ1- and ℓ2-observability
- Optimal decodability constant computable in polynomial time
- Applies to finite state, action, observation POMDPs
From the original article
1 min read at arxiv.orgWe study planning for finite-horizon partially observable Markov decision processes (POMDPs) with finite state, action, and observation spaces. Both exact and approximate planning are known to be computationally hard in this setting, so prior work has explored natural assumptions that make planning easier. Recent work [Golowich et al.
By Oliver Dobson · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.