Quasipolynomial-Time Planning for Decodable POMDPs
The paper gives an efficiently checkable condition for approximate planning that is strictly weaker than observability.
The authors give quasipolynomial-time approximate planning algorithms for finite-horizon POMDPs with any fixed positive decodability constant. Their condition follows from both ℓ₁- and ℓ₂-observability. The optimal decodability constant can be computed in polynomial time, while finding the optimal ℓ₁-observability constant is NP-hard in the worst case. They also show that a fast filter-forgetting guarantee used in earlier work does not extend directly to constant ℓ₂-observability.
ArXiv · AI/CL/LG's note
The authors give quasipolynomial-time approximate planning algorithms for finite-horizon POMDPs with any fixed positive decodability constant. Their condition follows from both ℓ₁- and ℓ₂-observability. The optimal decodability constant can be computed in polynomial time, while finding the optimal ℓ₁-observability constant is NP-hard in the worst case. They also show that a fast filter-forgetting guarantee used in earlier work does not extend directly to constant ℓ₂-observability.
ArXiv · AI/CL/LG's note
score 4