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

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.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