A POMDP Extension with Belief-dependent Rewards (Extended Version)

Mauricio Araya-López; Olivier Buffet; Vincent Thomas; François Charpillet

inria-00529498, version 2

A POMDP Extension with Belief-dependent Rewards (Extended Version)

Mauricio Araya-López ( Author to contact preferably )^a^, 1, Olivier Buffet ()^a^, 1, Vincent Thomas ()^b^, 1, François Charpillet ()^a^, 1

N° RR-7433 (2010)

Abstract: Partially Observable Markov Decision Processes (POMDPs) model sequential decision-making problems under uncertainty and partial observability. Unfortunately, some problems cannot be modeled with state-dependent reward functions, e.g., problems whose objective explicitly implies reducing the uncertainty on the state. To that end, we introduce ρPOMDPs, an extension of POMDPs where the reward function ρ depends on the belief state. We show that, under the common assumption that ρ is convex, the value function is also convex, what makes it possible to (1) approximate ρ arbitrarily well with a piecewise linear and convex (PWLC) function, and (2) use state-of-the-art exact or approximate solving algorithms with limited changes.

a – INRIA
b – Université Nancy II
1: MAIA (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00529498, version 2
http://hal.inria.fr/inria-00529498
oai:hal.inria.fr:inria-00529498
From: Olivier Buffet <>
Submitted on: Tuesday, 14 December 2010 16:48:53
Updated on: Wednesday, 15 December 2010 11:02:27

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%F inria-00529498, version 2
%0 Report
%U http://hal.inria.fr/inria-00529498
%2 INFO:INFO_AI
%T A POMDP Extension with Belief-dependent Rewards (Extended Version)
%A Araya-López, Mauricio
%A Buffet, Olivier
%A Thomas, Vincent
%A Charpillet, François
%+ MAIA - INRIA Lorraine - LORIA
%X Partially Observable Markov Decision Processes (POMDPs) model sequential decision-making problems under uncertainty and partial observability. Unfortunately, some problems cannot be modeled with state-dependent reward functions, e.g., problems whose objective explicitly implies reducing the uncertainty on the state. To that end, we introduce ρPOMDPs, an extension of POMDPs where the reward function ρ depends on the belief state. We show that, under the common assumption that ρ is convex, the value function is also convex, what makes it possible to (1) approximate ρ arbitrarily well with a piecewise linear and convex (PWLC) function, and (2) use state-of-the-art exact or approximate solving algorithms with limited changes.
%2 Les processus de décision markoviens partiellement observables (POMDP) modélisent des problèmes de décision sous incertitude et observabilité partielle. Malheureusement, certains problèmes ne peuvent être modélisés avec des fonctions de récompensent dépendant des états, par exemple, des problèmes dont l'objectif implique explicitement de réduire l'incertitude sur l'état. A cette n, nous introduisons les ρPOMDP, une extension des POMDP dans laquelle la fonction de récompense ρ dépend de l'état de croyance. Nous montrons que, sous l'hypothèse courante que ρ est convexe, la fonction de valeur est aussi convexe, ce qui rend possible (1) d'approximer ρ arbitrairement bien avec une fonction linéaire par morceaux et convexe (PWLC), et (2) d'utiliser des algorithmes de résolution exacts ou approchés de l'état de l'art après des modications limitées.
%G English
%2 Research Report
%P 18
%8 2010-10-22
%K partially observable Markov decision processes; reward function; active sensing; piecewise linear and convex approximation
%Z RR-7433

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00529498"><monogr>
<author><persName><forename>Mauricio</forename><surname>Araya-López</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Olivier</forename><surname>Buffet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Vincent</forename><surname>Thomas</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>François</forename><surname>Charpillet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">MAIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="m">A POMDP Extension with Belief-dependent Rewards (Extended Version)</title><title type="main" level="m">A POMDP Extension with Belief-dependent Rewards (Extended Version)</title><imprint><biblScope type="publicationDate">2010-10-22</biblScope><biblScope type="pp">18</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00529498</idno><idno type="HALFile">http://hal.inria.fr/inria-00529498/PDF/RR-7433.pdf</idno></biblStruct>
</listBibl>
</listBibl>