Partially observable Markov decision process

A discrete-time POMDP models the relationship between an agent and its environment. Formally, a POMDP is a 7-tuple ${\displaystyle (S,A,T,R,\Omega ,O,\gamma )}$, where

• ${\displaystyle S}$ is a set of states,
• ${\displaystyle A}$ is a set of actions,
• ${\displaystyle T}$ is a set of conditional transition probabilities between states,
• ${\displaystyle R:S\times A\to \mathbb {R} }$ is the reward function.
• ${\displaystyle \Omega }$ is a set of observations,
• ${\displaystyle O}$ is a set of conditional observation probabilities, and
• ${\displaystyle \gamma \in [0,1]}$ is the discount factor.

At each time period, the environment is in some state ${\displaystyle s\in S}$. The agent takes an action ${\displaystyle a\in A}$, which causes the environment to transition to state ${\displaystyle s'}$ with probability ${\displaystyle T(s'\mid s,a)}$. At the same time, the agent receives an observation ${\displaystyle o\in \Omega }$ which depends on the new state of the environment, ${\displaystyle s'}$, and on the just taken action, ${\displaystyle a}$, with probability ${\displaystyle O(o\mid s',a)}$. Finally, the agent receives a reward ${\displaystyle r}$ equal to ${\displaystyle R(s,a)}$. Then the process repeats. The goal is for the agent to choose actions at each time step that maximize its expected future discounted reward: ${\displaystyle E\left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\right]}$, where ${\displaystyle r_{t}}$ is the reward earned at time ${\displaystyle t}$. The discount factor ${\displaystyle \gamma }$ determines how much immediate rewards are favored over more distant rewards. When ${\displaystyle \gamma =0}$ the agent only cares about which action will yield the largest expected immediate reward; when ${\displaystyle \gamma =1}$ the agent cares about maximizing the expected sum of future rewards.

Because the agent does not directly observe the environment's state, the agent must make decisions under uncertainty of the true environment state. However, by interacting with the environment and receiving observations, the agent may update its belief in the true state by updating the probability distribution of the current state. A consequence of this property is that the optimal behavior may often include (information gathering) actions that are taken purely because they improve the agent's estimate of the current state, thereby allowing it to make better decisions in the future.

It is instructive to compare the above definition with the definition of a Markov decision process. An MDP does not include the observation set, because the agent always knows with certainty the environment's current state. Alternatively, an MDP can be reformulated as a POMDP by setting the observation set to be equal to the set of states and defining the observation conditional probabilities to deterministically select the observation that corresponds to the true state.

Unlike the "originating" POMDP (where each action is available from only one state), in the corresponding Belief MDP all belief states allow all actions, since you (almost) always have some probability of believing you are in any (originating) state. As such, ${\displaystyle \pi }$ specifies an action ${\displaystyle a=\pi (b)}$ for any belief ${\displaystyle b}$.

Here it is assumed the objective is to maximize the expected total discounted reward over an infinite horizon. When ${\displaystyle R}$ defines a cost, the objective becomes the minimization of the expected cost.

The expected reward for policy ${\displaystyle \pi }$ starting from belief ${\displaystyle b_{0}}$ is defined as

${\displaystyle V^{\pi }(b_{0})=\sum _{t=0}^{\infty }\gamma ^{t}r(b_{t},a_{t})=\sum _{t=0}^{\infty }\gamma ^{t}E{\Bigl [}R(s_{t},a_{t})\mid b_{0},\pi {\Bigr ]}}$

where ${\displaystyle \gamma <1}$ is the discount factor. The optimal policy ${\displaystyle \pi ^{*}}$ is obtained by optimizing the long-term reward.

${\displaystyle \pi ^{*}={\underset {\pi }{\mbox{argmax}}}\ V^{\pi }(b_{0})}$

where ${\displaystyle b_{0}}$ is the initial belief.

The optimal policy, denoted by ${\displaystyle \pi ^{*}}$, yields the highest expected reward value for each belief state, compactly represented by the optimal value function ${\displaystyle V^{*}}$. This value function is solution to the Bellman optimality equation:

${\displaystyle V^{*}(b)=\max _{a\in A}{\Bigl [}r(b,a)+\gamma \sum _{o\in \Omega }\Pr(o\mid b,a)V^{*}(\tau (b,a,o)){\Bigr ]}}$

For finite-horizon POMDPs, the optimal value function is piecewise-linear and convex.[3] It can be represented as a finite set of vectors. In the infinite-horizon formulation, a finite vector set can approximate ${\displaystyle V^{*}}$ arbitrarily closely, whose shape remains convex. Value iteration applies dynamic programming update to gradually improve on the value until convergence to an ${\displaystyle \epsilon }$-optimal value function, and preserves its piecewise linearity and convexity.[4] By improving the value, the policy is implicitly improved. Another dynamic programming technique called policy iteration explicitly represents and improves the policy instead.[5][6]