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 (Åström 1965) 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 (Kaelbling, Littman, and Cassandra 1998).

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:

Define a POMDP problem using the function POMDP(), and
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.

str(args(POMDP))

## function (states, actions, observations, transition_prob, observation_prob, 
##     reward, discount = 0.9, horizon = Inf, terminal_values = NULL, start = "uniform", 
##     name = NA)

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.
```
start = c(0.5 , 0.3 , 0.2)
```
The string ‘“uniform”’ for a uniform distribution over all states.
```
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:
```
start = 3
start = c(1, 3)
```
A vector of strings specifying a subset as equally likely start states.
```
start <- "state3"
start <- c("state1" , "state3") 
```
A vector of strings starting with "-" specifying which states to exclude from the uniform initial probability distribution.
```
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.

str(args(solve_POMDP))

## function (model, horizon = NULL, discount = NULL, terminal_values = NULL, 
##     method = "grid", digits = 7, parameter = NULL, verbose = FALSE)

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’. 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 (Cassandra, Kaelbling, and Littman 1994). 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.

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

## POMDP, list - Tiger Problem
##   Discount factor: 0.75
##   Horizon: Inf epochs
##   List components: 'name', 'discount', 'horizon', 'states', 'actions',
##     'observations', 'transition_prob', 'observation_prob', 'reward',
##     'start', 'terminal_values'

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.

sol <- solve_POMDP(Tiger)
sol

## POMDP, list - Tiger Problem
##   Discount factor: 0.75
##   Horizon: Inf epochs
##   Solved:
##     Solution converged: TRUE
##     Total expected reward: 1.933439
##   List components: 'name', 'discount', 'horizon', 'states', 'actions',
##     'observations', 'transition_prob', 'observation_prob', 'reward',
##     'start', 'solution', 'solver_output'

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.

sol$solution

## $method
## [1] "grid"
## 
## $parameter
## NULL
## 
## $converged
## [1] TRUE
## 
## $total_expected_reward
## [1] 1.933439
## 
## $initial_belief
##  tiger-left tiger-right 
##         0.5         0.5 
## 
## $initial_pg_node
## [1] 3
## 
## $belief_states
##         tiger-left  tiger-right
##  [1,] 5.000000e-01 5.000000e-01
##  [2,] 8.500000e-01 1.500000e-01
##  [3,] 1.500000e-01 8.500000e-01
##  [4,] 9.697987e-01 3.020134e-02
##  [5,] 3.020134e-02 9.697987e-01
##  [6,] 9.945344e-01 5.465587e-03
##  [7,] 5.465587e-03 9.945344e-01
##  [8,] 9.990311e-01 9.688763e-04
##  [9,] 9.688763e-04 9.990311e-01
## [10,] 9.998289e-01 1.711147e-04
## [11,] 1.711147e-04 9.998289e-01
## [12,] 9.999698e-01 3.020097e-05
## [13,] 3.020097e-05 9.999698e-01
## [14,] 9.999947e-01 5.329715e-06
## [15,] 5.329715e-06 9.999947e-01
## [16,] 9.999991e-01 9.405421e-07
## [17,] 9.405421e-07 9.999991e-01
## [18,] 9.999998e-01 1.659782e-07
## [19,] 1.659782e-07 9.999998e-01
## [20,] 1.000000e+00 2.929027e-08
## [21,] 2.929027e-08 1.000000e+00
## [22,] 1.000000e+00 5.168871e-09
## [23,] 5.168871e-09 1.000000e+00
## [24,] 1.000000e+00 9.121536e-10
## [25,] 9.121536e-10 1.000000e+00
## 
## $pg
## $pg[[1]]
##   node     action tiger-left tiger-right
## 1    1  open-left          3           3
## 2    2     listen          3           1
## 3    3     listen          4           2
## 4    4     listen          5           3
## 5    5 open-right          3           3
## 
## 
## $alpha
## $alpha[[1]]
##      tiger-left tiger-right
## [1,] -98.549921   11.450079
## [2,] -10.854299    6.516937
## [3,]   1.933439    1.933439
## [4,]   6.516937  -10.854299
## [5,]  11.450079  -98.549921
## 
## 
## $policy
## $policy[[1]]
##   tiger-left tiger-right     action
## 1 -98.549921   11.450079  open-left
## 2 -10.854299    6.516937     listen
## 3   1.933439    1.933439     listen
## 4   6.516937  -10.854299     listen
## 5  11.450079  -98.549921 open-right
## 
## 
## attr(,"class")
## [1] "POMDP_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 ingormation 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.

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.

alpha <- sol$solution$alpha
alpha

## [[1]]
##      tiger-left tiger-right
## [1,] -98.549921   11.450079
## [2,] -10.854299    6.516937
## [3,]   1.933439    1.933439
## [4,]   6.516937  -10.854299
## [5,]  11.450079  -98.549921

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

Åström, K. J. 1965. “Optimal Control of Markov Processes with Incomplete State Information.” Journal of Mathematical Analysis and Applications 10 (1): 174–205. https://doi.org/https://doi.org/10.1016/0022-247X(65)90154-X.

Boettiger, Carl, Jeroen Ooms, and Milad Memarzadeh. 2021. Sarsop: Approximate Pomdp Planning Software. https://CRAN.R-project.org/package=sarsop.

Cassandra, Anthony R. 2015. “The POMDP Page.” https://www.pomdp.org.

Cassandra, Anthony R., Leslie Pack Kaelbling, and Michael L. Littman. 1994. “Acting Optimally in Partially Observable Stochastic Domains.” In Proceedings of the Twelfth National Conference on Artificial Intelligence. Seattle, WA.

Cassandra, Anthony R., Michael L. Littman, and Nevin Lianwen Zhang. 1997. “Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes.” In UAI’97: Proceedings of the Thirteenth Conference on Uncertainty in Artificial Intelligence, 54–61.

Kaelbling, Leslie Pack, Michael L. Littman, and Anthony R. Cassandra. 1998. “Planning and Acting in Partially Observable Stochastic Domains.” Artificial Intelligence 101 (1): 99–134. https://doi.org/10.1016/S0004-3702(98)00023-X.

Kurniawati, Hanna, David Hsu, and Wee Sun Lee. 2008. “SARSOP: Efficient Point-Based Pomdp Planning by Approximating Optimally Reachable Belief Spaces.” In In Proc. Robotics: Science and Systems.

Littman, Michael L., Anthony R. Cassandra, and Leslie Pack Kaelbling. 1995. “Learning Policies for Partially Observable Environments: Scaling up.” In Proceedings of the Twelfth International Conference on International Conference on Machine Learning, 362–70. ICML’95. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Pineau, Joelle, Geoff Gordon, and Sebastian Thrun. 2003. “Point-Based Value Iteration: An Anytime Algorithm for Pomdps.” In Proceedings of the 18th International Joint Conference on Artificial Intelligence, 1025–30. IJCAI’03. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Sondik, E. J. 1971. “The Optimal Control of Partially Observable Markov Decision Processes.” PhD thesis, Stanford, California.

Zhang, Nevin L., and Wenju Liu. 1996. “Planning in Stochastic Domains: Problem Characteristics and Approximation.” HKUST-CS96-31. Hong Kong University.

POMDP: Introduction to Partially Observable Markov Decision Processes

Michael Hahsler and Hossein Kamalzadeh

May 20, 2021

Introduction