---
title: "pomdp: Introduction to Partially Observable Markov Decision Processes"
author: "Michael Hahsler and Hossein Kamalzadeh"
bibliography: references.bib
vignette: >
%\VignetteIndexEntry{pomdp: Introduction to Partially Observable Markov Decision Processes}
%\VignetteEngine{knitr::rmarkdown}
%\VignetteEncoding{UTF-8}
output:
rmarkdown::html_vignette
---
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>"
)
```
```{r setup}
library("pomdp")
```
# Introduction
The R package **pomdp** [@Hahsler2024] provides the infrastructure to define and
analyze the solutions of Partially Observable Markov Decision Processes
(POMDP) models. The package is a companion to package **pomdpSolve**
which provides the executable for
'[pomdp-solve](http://www.pomdp.org/code/)' [@Cassandra2015], a
well-known fast C implementation of a variety of algorithms to solve
POMDPs. **pomdp** can also use package **sarsop** [@Bottiger2021] which
provides an implementation of the SARSOP (Successive Approximations of
the Reachable Space under Optimal Policies) algorithm.
The package provides the following algorithms:
- Exact value iteration
- **Enumeration algorithm** [@Sondik1971].
- **Two pass algorithm** [@Sondik1971].
- **Witness algorithm** [@Littman1995].
- **Incremental pruning algorithm** [@Zhang1996],
[@Cassandra1997].
- Approximate value iteration
- **Finite grid algorithm** [@Cassandra2015], a variation of
point-based value iteration to solve larger POMDPs (**PBVI**;
see [@Pineau2003]) without dynamic belief set expansion.
- **SARSOP** [@Kurniawati2008], Successive Approximations of the
Reachable Space under Optimal Policies, a point-based algorithm
that approximates optimally reachable belief spaces for
infinite-horizon problems (via package **sarsop**
[@Bottiger2021]).
The package enables the user to simply define all components of a POMDP
model and solve the problem using several methods. The package also
contains functions to analyze and visualize the POMDP solutions (e.g.,
the optimal policy) and extends to regular MDPs.
In this document, we will give a very brief introduction to the concept
of POMDPs, describe the features of the R package, and illustrate the
usage with a toy example.
# Partially Observable Markov Decision Processes
A partially observable Markov decision process (POMDP) is a combination
of an regular Markov Decision Process to model system dynamics with a
hidden Markov model that connects unobservable system states
probabilistically to observations.
The agent can perform actions which affect the system (i.e., may cause
the system state to change) with the goal to maximize the expected
future rewards that depend on the sequence of system state and the
agent's actions in the future. The goal is to find the optimal policy
that guides the agent's actions. Different to MDPs, for POMDPs, the
agent cannot directly observe the complete system state, but the agent
makes observations that depend on the state. The agent uses these
observations to form a belief about in what state the system currently
is. This belief is called a belief state and is expressed as a
probability distribution over all possible states. The solution of the
POMDP is a policy prescribing which action to take in each belief state.
Note that belief states are continuous resulting in an infinite state
set which makes POMDPs much harder to solve compared to MDPs.
The POMDP framework is general enough to model a variety of real-world
sequential decision-making problems. Applications include robot
navigation problems, machine maintenance, and planning under uncertainty
in general. The general framework of Markov decision processes with
incomplete information was described by Karl Johan Åström [@Astrom1965]
in the case of a discrete state space, and it was further studied in the
operations research community where the acronym POMDP was coined. It was
later adapted for problems in artificial intelligence and automated
planning by Leslie P. Kaelbling and Michael L. Littman [@Kaelbling1998].
A discrete-time POMDP can formally be described as a 7-tuple
$$\mathcal{P} = (S, A, T, R, \Omega , O, \gamma),$$ where
- $S = \{s_1, s_2, \dots, s_n\}$ is a set of partially observable
states,
- $A = \{a_1, a_2, \dots, a_m\}$ is a set of actions,
- $T$ a set of conditional transition probabilities $T(s' \mid s,a)$
for the state transition $s \rightarrow s'$ conditioned on the taken
action.
- $R: S \times A \rightarrow \mathbb{R}$ is the reward function,
- $\Omega = \{o_1, o_2, \dots, o_k\}$ is a set of observations,
- $O$ is a set of observation probabilities $O(o \mid s',a)$
conditioned on the reached state and the taken action, and
- $\gamma \in [0, 1]$ is the discount factor.
At each time period, the environment is in some unknown state $s \in S$.
The agent chooses an action $a \in A$, which causes the environment to
transition to state $s' \in S$ with probability $T(s' \mid s,a)$. At the
same time, the agent receives an observation $o \in \Omega$ which
depends on the new state of the environment with probability
$O(o \mid s',a)$. Finally, the agent receives a reward $R(s,a)$. Then
the process repeats. The goal is for the agent to choose actions that
maximizes the expected sum of discounted future rewards, i.e., she
chooses the actions at each time $t$ that
$$\max E\left[\sum_{t=0}^{\infty} \gamma^t R(s_t, a_t)\right].$$
For a finite time horizon, only the expectation over the sum up to the
time horizon is used.
# Package Functionality
Solving a POMDP problem with the **pomdp** package consists of two
steps:
1. Define a POMDP problem using the function `POMDP()`, and\
2. solve the problem using `solve_POMDP()`.
## Defining a POMDP Problem
The `POMDP()` function has the following arguments, each corresponds to
one of the elements of a POMDP.
```{r}
str(args(POMDP))
```
where
- `states` defines the set of states $S$,
- `actions` defines the set of actions $A$,
- `observations` defines the set of observations $\Omega$,
- `transition_prob` defines the conditional transition probabilities
$T(s' \mid s,a)$,
- `observation_prob` specifies the conditional observation
probabilities $O(o \mid s',a)$,
- `reward` specifies the reward function $R$,
- `discount` is the discount factor $\gamma$ in range $[0,1]$,
- `horizon` is the problem horizon as the number of periods to
consider.
- `terminal_values` is a vector of state utilities at the end of the
horizon.
- `start` is the initial probability distribution over the system
states $S$,
- `max` indicates whether the problem is a maximization or a
minimization, and
- `name` used to give the POMDP problem a name.
While specifying the discount rate and the set of states, observations
and actions is straight-forward. Some arguments can be specified in
different ways. The initial belief state `start` can be specified as
- A vector of $n$ probabilities in $[0,1]$, that add up to 1, where
$n$ is the number of states.
```{r, eval = FALSE}
start = c(0.5 , 0.3 , 0.2)
```
- The string '"uniform"' for a uniform distribution over all states.
```{r, eval = FALSE}
start = "uniform"
```
- A vector of integer indices specifying a subset as start states. The
initial probability is uniform over these states. For example, only
state 3 or state 1 and 3:
```{r, eval = FALSE}
start = 3
start = c(1, 3)
```
- A vector of strings specifying a subset as equally likely start
states.
```{r, eval = FALSE}
start <- "state3"
start <- c("state1" , "state3")
```
- A vector of strings starting with `"-"` specifying which states to
exclude from the uniform initial probability distribution.
```{r, eval = FALSE}
start = c("-" , "state2")
```
The transition probabilities (`transition_prob`), observation
probabilities (`observation_prob`) and reward function (`reward`) can be
specified in several ways:
- As a `data.frame` created using `rbind()` and the helper functions
`T_()`, `O_()` and `R_()`.
- A named list of matrices representing the transition probabilities
or rewards.
- A function with the same arguments `T_()`, `O_()` or `R_()` that
returns the probability or reward.
More details can be found in the manual page for `POMDP()`.
## Solving a POMDP
POMDP problems are solved with the function `solve_POMDP()` with the
following arguments.
```{r}
str(args(solve_POMDP))
```
The `model` argument is a POMDP problem created using the `POMDP()`
function, but it can also be the name of a POMDP file using the format
described in the [file specification section of
'pomdp-solve](http://www.pomdp.org/code/pomdp-file-spec.html)'. The
`horizon` argument specifies the finite time horizon (i.e, the number of
time steps) considered in solving the problem. If the horizon is
unspecified (i.e., `NULL`), then the algorithm continues running
iterations till it converges to the infinite horizon solution. The
`method` argument specifies what algorithm the solver should use.
Available methods including `"grid"`, `"enum"`, `"twopass"`,
`"witness"`, and `"incprune"`. Further solver parameters can be
specified as a list in `parameters`. The list of available parameters
can be obtained using the function `solve_POMDP_parameter()`. Details on
the other arguments can be found in the manual page for
\`solve_POMDP()\`.
# The Tiger Problem Example
We will demonstrate how to use the package with the Tiger Problem
[@Cassandra1994]. The problem is defined as:
> An agent is facing two closed doors and a tiger is put with equal
> probability behind one of the two doors represented by the states
> `tiger-left` and `tiger-right`, while treasure is put behind the other
> door. The possible actions are `listen` for tiger noises or opening a
> door (actions `open-left` and `open-right`). Listening is neither free
> (the action has a reward of -1) nor is it entirely accurate. There is
> a 15% probability that the agent hears the tiger behind the left door
> while it is actually behind the right door and vice versa. If the
> agent opens door with the tiger, it will get hurt (a negative reward
> of -100), but if it opens the door with the treasure, it will receive
> a positive reward of 10. After a door is opened, the problem is
> reset(i.e., the tiger is randomly assigned to a door with chance
> 50/50) and the the agent gets another try.
## Specifying the Tiger Problem
The problem can be specified using function `POMDP()` as follows.
```{r}
library("pomdp")
Tiger <- POMDP(
name = "Tiger Problem",
discount = 0.75,
states = c("tiger-left" , "tiger-right"),
actions = c("listen", "open-left", "open-right"),
observations = c("tiger-left", "tiger-right"),
start = "uniform",
transition_prob = list(
"listen" = "identity",
"open-left" = "uniform",
"open-right" = "uniform"),
observation_prob = list(
"listen" = matrix(c(0.85, 0.15, 0.15, 0.85), nrow = 2, byrow = TRUE),
"open-left" = "uniform",
"open-right" = "uniform"),
reward = rbind(
R_("listen", "*", "*", "*", -1 ),
R_("open-left", "tiger-left", "*", "*", -100),
R_("open-left", "tiger-right", "*", "*", 10 ),
R_("open-right", "tiger-left", "*", "*", 10 ),
R_("open-right", "tiger-right", "*", "*", -100)
)
)
Tiger
```
Note that we use for each component the way that lets us specify the
problem in the easiest way (i.e., for observations and transitions a
list and for rewards a data frame created with the `R_()` function).
## Solving the Tiger Problem
Now, we can solve the problem. We use the default method (finite grid)
which implements a form of point-based value iteration that can find
approximate solutions also for larger problems.
```{r}
sol <- solve_POMDP(Tiger)
sol
```
The output is an object of class POMDP which contains the solution as an
additional list component. The solution can be accessed directly in the
list.
```{r}
sol$solution
```
The solution contains the following elements:
- **`total_expected_reward`:** The total expected reward of the
optimal solution.
- **`initial_belief_state`:** The index of the node in the policy
graph that represents the initial belief state.
- **`belief_states`:** A data frame of all the belief states (rows)
used while solving the problem. There is a column at the end that
indicates which node in the policy graph is associated with the
belief state. That is which segment in the value function (specified
in **alpha** below) provides the best value for the given belief
state.
- **`pg`:** A data frame containing the optimal policy graph. Rows are
nodes in the graph are segments in the value function and each
represents one or more belief states. Column two indicates the
optimal action for the node. Columns three and after represent the
transitions to new nodes in the policy graph depending on the next
observation.
- **`alpha`:** A data frame with the coefficients of the optimal
hyperplanes for the value function.
- **`policy`:** A data frame that combines the information from `pg`
and `alpha`. The first few columns specifying the belief state
(hyperplane from `alpha`) and the last column indicates the optimal
action (from `pg`).
## Visualization
In this section, we will visualize the policy graph provided in the
solution by the `solve_POMDP()` function.
```{r fig.width = 10, fig.asp = .7}
plot_policy_graph(sol)
```
The policy graph can be easily interpreted. Without prior information,
the agent starts at the node marked with "initial belief." In this case
the agent beliefs that there is a 50-50 chance that the tiger is behind
ether door. The optimal action is displayed inside the state and in this
case is to listen. The observations are labels on the arcs. Let us
assume that the observation is "tiger-left", then the agent follows the
appropriate arc and ends in a node representing a belief (one ore more
belief states) that has a very high probability of the tiger being left.
However, the optimal action is still to listen. If the agent again hears
the tiger on the left then it ends up in a note that has a close to 100%
belief that the tiger is to the left and `open-right` is the optimal
action. The are arcs back from the nodes with the open actions to the
initial state reset the problem.
Since we only have two states, we can visualize the piecewise linear
convex value function as a simple plot.
```{r}
alpha <- sol$solution$alpha
alpha
plot_value_function(sol, ylim = c(0,20))
```
The lines represent the nodes in the policy graph and the optimal
actions are shown in the legend.
# References