Finite partially observable Markov decision process

Let $S$ be a finite nonempty set of hidden states, $A$ a finite nonempty action set available in every state, and $\mathrm{\Omega }$ a finite nonempty observation set. Give these sets their power-set sigma-algebras. A finite POMDP with known model consists of a finite reward alphabet $\mathcal{R}\subseteq \mathbb{R}$ and a joint probability mass $p(s^{\mathrm{\prime }},\rho \mid s,a)$ on $S\times \mathcal{R}$ for each $(s,a)\in S\times A$, an observation probability distribution $O(\cdot \mid s^{\mathrm{\prime }})$ on $\mathrm{\Omega }$ for each $s^{\mathrm{\prime }}\in S$, and an initial belief $b_0:S\to [0,1]$ with ${\sum }_{s\in S}{b}_0(s)=1$. Put

$T(s^{\mathrm{\prime }}\mid s,a)={\sum }_{\rho \in \mathcal{R}}p(s^{\mathrm{\prime }},\rho \mid s,a),r(s,a)={\sum }_{s^{\mathrm{\prime }}\in S}{\sum }_{\rho \in \mathcal{R}}\rho p(s^{\mathrm{\prime }},\rho \mid s,a)\mathrm{.}$

At decision time $t$, write $S_t\in S$ for the hidden state, $A_t\in A$ for the chosen action, $R_t\in \mathcal{R}$ for the realized reward, and $O_{t+1}\in \mathrm{\Omega }$ for the next observation. Conditional on $S_t=s$ and $A_t=a$, the joint law of next state $S_{t+1}=s^{\mathrm{\prime }}$, reward $R_t=\rho$, and observation $O_{t+1}=o$ is $p(s^{\mathrm{\prime }},\rho \mid s,a)O(o\mid s^{\mathrm{\prime }})$. Thus the observation depends only on the next state and is not an additional observation of the reward. A policy uses only the past actions and observations; realized rewards are not included in its history. For a horizon $H\in \mathbb{N}$ and discount $\gamma \in [0,1]$, the objective is to maximize $\mathbb{E}[{\sum }_{t=0}^{H-1}{\gamma }^t{R}_t]$. The model is known; learning its transition, reward, or observation laws is outside this definition.

A finite MDP has finite state and reward sets, nonempty finite action sets, a joint next-state/reward law, and the transition and expected-reward marginals used here.

A probability kernel assigns a probability measure at every input and has measurable event sections.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.

Tedrake, MIT Underactuated Robotics course notes.

Poupart, University of Waterloo CS 886 Lecture 13.