Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Tighter Value-Function Approximations for POMDPs

Krale, Merlijn ; Koops, Wietze LU orcid ; Junges, Sebastian ; Simão, Thiago D. and Jansen, Nils (2025) 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025 In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS p.1200-1208
Abstract

Solving partially observable Markov decision processes (POMDPs) typically requires reasoning about the values of exponentially many state beliefs. Towards practical performance, state-of-the-art solvers use value bounds to guide this reasoning. However, sound upper value bounds are often computationally expensive to compute, and there is a tradeoff between the tightness of such bounds and their computational cost. This paper introduces new and provably tighter upper value bounds than the commonly used fast informed bound. Our empirical evaluation shows that, despite their additional computational overhead, the new upper bounds accelerate state-of-the-art POMDP solvers on a wide range of benchmarks.

Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Heuristic Search, Planning, POMDPs, Value Bounds
host publication
Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025
series title
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
editor
Vorobeychik, Yevgeniy ; Das, Sanmay and Nowe, Ann
pages
9 pages
publisher
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
conference name
24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025
conference location
Detroit, United States
conference dates
2025-05-19 - 2025-05-23
external identifiers
  • scopus:105009828484
ISSN
1558-2914
1548-8403
ISBN
9798400714269
language
English
LU publication?
yes
additional info
Publisher Copyright: © 2025 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org).
id
c4edf905-ccf8-4c0b-99b1-1e9d2e0baac0
date added to LUP
2026-01-20 16:13:10
date last changed
2026-01-21 03:49:07
@inproceedings{c4edf905-ccf8-4c0b-99b1-1e9d2e0baac0,
  abstract     = {{<p>Solving partially observable Markov decision processes (POMDPs) typically requires reasoning about the values of exponentially many state beliefs. Towards practical performance, state-of-the-art solvers use value bounds to guide this reasoning. However, sound upper value bounds are often computationally expensive to compute, and there is a tradeoff between the tightness of such bounds and their computational cost. This paper introduces new and provably tighter upper value bounds than the commonly used fast informed bound. Our empirical evaluation shows that, despite their additional computational overhead, the new upper bounds accelerate state-of-the-art POMDP solvers on a wide range of benchmarks.</p>}},
  author       = {{Krale, Merlijn and Koops, Wietze and Junges, Sebastian and Simão, Thiago D. and Jansen, Nils}},
  booktitle    = {{Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2025}},
  editor       = {{Vorobeychik, Yevgeniy and Das, Sanmay and Nowe, Ann}},
  isbn         = {{9798400714269}},
  issn         = {{1558-2914}},
  keywords     = {{Heuristic Search; Planning; POMDPs; Value Bounds}},
  language     = {{eng}},
  pages        = {{1200--1208}},
  publisher    = {{International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)}},
  series       = {{Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS}},
  title        = {{Tighter Value-Function Approximations for POMDPs}},
  year         = {{2025}},
}