Online Learning for Unknown Partially Observable MDPs

Reinforcement learning (RL) considers the sequential decision-making problem of an agent in an unknown environment with the goal of minimizing the total cost. The agent faces a fundamental exploration-exploitation trade-off: should it exploit the available information to minimize the cost or should it explore the environment to gather more information for future decisions? Maintaining a proper balance between exploration and exploitation is a fundamental challenge in RL and is measured with the notion of cumulative regret: the difference between the cumulative cost of the learning algorithm and that of the best policy.

The problem of balancing exploration and exploitation in RL has been successfully addressed for MDPs and algorithms with near optimal regret bounds known (Bartlett and Tewari, 2009; Jaksch et al., 2010; Ouyang et al., 2017b; Azar et al., 2017; Fruit et al., 2018; Jin et al., 2018; Abbasi-Yadkori et al., 2019b; Zhang and Ji, 2019; Zanette and Brunskill, 2019; Hao et al., 2020; Wei et al., 2020, 2021). MDPs assume that the state is perfectly observable by the agent and the only uncertainty is about the underlying dynamics of the environment. However, in many real-world scenarios such as robotics, healthcare and finance, the state is not fully observed by the agent, and only a partial observation is available. These scenarios are modeled by Partially Observable Markov Decision Processes (POMDPs). In addition to the uncertainty in the environment dynamics, the agent has to deal with the uncertainty about the underlying state. It is well known (Kumar and Varaiya, 2015) that introducing an information or belief state (a posterior distribution over the states given the history of observations and actions) allows the POMDP to be recast as an MDP over the belief state space. The resulting algorithm requires a posterior update of the belief state which needs the transition and observation model to be fully known. This presents a significant difficulty when the model parameters are unknown. Thus, managing the exploration-exploitation trade-off for POMDPs is a significant challenge and to the best of our knowledge, no online RL algorithm with sub-linear regret is known.

In this paper, we consider infinite-horizon average-cost POMDPs with finite states, actions and observations. The underlying state transition dynamics is unknown, though we assume the observation kernel to be known. We propose a Posterior Sampling Reinforcement Learning algorithm (PSRL-POMDP) and prove that it achieves a Bayesian expected regret bound of $\mathcal{O}(\log T)$ in the finite (transition kernel) parameter set case where $T$ is the time horizon. We then show that in the general (continuous parameter set) case, it achieves $\tilde{\mathcal{O}}(T^{2/3})$ under some technical assumptions. The PSRL-POMDP algorithm is a natural extension of the TSDE algorithm for MDPs (Ouyang et al., 2017b) with two main differences. First, in addition to the posterior distribution on the environment dynamics, the algorithm maintains a posterior distribution on the underlying state. Second, since the state is not fully observable, the agent cannot keep track of the number of visits to state-action pairs, a quantity that is crucial in the design of algorithms for tabular MDPs. Instead, we introduce a notion of pseudo count and carefully handle its relation with the true counts to obtain sub-linear regret. To the best of our knowledge, PSRL-POMDP is the first online RL algorithm for POMDPs with sub-linear regret.

An infinite-horizon average-cost Partially Observable Markov Decision Process (POMDP) can be specified by $({\mathcal{S}},{\mathcal{A}},\theta,C,O,\eta)$ where ${\mathcal{S}}$ is the state space, ${\mathcal{A}}$ is the action space, $C:{\mathcal{S}}\times{\mathcal{A}}\to[0,1]$ is the cost function, and $O$ is the set of observations. Here $\eta:{\mathcal{S}}\to\Delta_{O}$ is the observation kernel, and $\theta:{\mathcal{S}}\times{\mathcal{A}}\to\Delta_{\mathcal{S}}$ is the transition kernel such that $\eta(o|s)=\mathbb{P}(o_{t}=o|s_{t}=s)$ and $\theta(s^{\prime}|s,a)=\mathbb{P}(s_{t+1}=s^{\prime}|s_{t}=s,a_{t}=a)$ where $o_{t}\in O$, $s_{t}\in{\mathcal{S}}$ and $a_{t}\in{\mathcal{A}}$ are the observation, state and action at time $t=1,2,3,\cdots$. Here, for a finite set ${\mathcal{X}}$, $\Delta_{\mathcal{X}}$ is the set of all probability distributions on ${\mathcal{X}}$. We assume that the state space, the action space and the observations are finite with size $|{\mathcal{S}}|,|{\mathcal{A}}|,|O|$, respectively.

Let ${\mathcal{F}}_{t}$ be the information available at time $t$ (prior to action $a_{t}$), i.e., the sigma algebra generated by the history of actions and observations $a_{1},o_{1},\cdots,a_{t-1},o_{t-1},o_{t}$ and let ${\mathcal{F}}_{t+}$ be the information after choosing action $a_{t}$. Unlike MDPs, the state is not observable by the agent and the optimal policy cannot be a function of the state. Instead, the agent maintains a belief $h_{t}(\cdot;\theta)\in\Delta_{\mathcal{S}}$ given by $h_{t}(s;\theta):=\mathbb{P}(s_{t}=s|{\mathcal{F}}_{t};\theta)$, as a sufficient statistic for the history of observations and actions. Here we use the notation $h_{t}(\cdot;\theta)$ to explicitly show the dependency of the belief on $\theta$. After taking action $a_{t}$ and observing $o_{t+1}$, the belief $h_{t}$ can be updated as

This update rule is compactly denoted by $h_{t+1}(\cdot;\theta)=\tau(h_{t}(\cdot;\theta),a_{t},o_{t+1};\theta)$, with the initial condition

where $h(\cdot;\theta)$ is the distribution of the initial state $s_{1}$ (denoted by $s_{1}\sim h$). A deterministic stationary policy $\pi:\Delta_{\mathcal{S}}\to{\mathcal{A}}$ maps a belief to an action. The long-term average cost of a policy $\pi$ can be defined as

Let $J(h,\theta):=\inf_{\pi}J_{\pi}(h,\theta)$ be the optimal long-term average cost that in general may depend on the initial state distribution $h$, though we will assume it is independent of the initial distribution $h$ (and thus denoted by $J(\theta)$), and the following Bellman equation holds:

where $v$ is called the relative value function, $b^{\prime}=\tau(b,a,o;\theta)$ is the updated belief, $c(b,a):=\sum_{s}C(s,a)b(s)$ is the expected cost, and $P(o|b,a;\theta)$ is the probability of observing $o$ in the next step, conditioned on the current belief $b$ and action $a$, i.e.,

Various conditions are known under which Assumption 1 holds, e.g., when the MDP is weakly communicating (Bertsekas, 2017). Note that if Assumption 1 holds, the policy $\pi^{*}$ that minimizes the right hand side of (3) is the optimal policy. More precisely,

Note that if $v$ satisfies the Bellman equation, so does $v$ plus any constant. Therefore, without loss of generality, and since $v$ is bounded, we can assume that $\inf_{b\in\Delta_{\mathcal{S}}}v(b;\theta)=0$ and define the span of a POMDP as $\operatorname*{sp}(\theta):=\sup_{b\in\Delta_{\mathcal{S}}}v(b;\theta)$. Let $\Theta_{H}$ be the class of POMDPs that satisfy Assumption 1 and have $\operatorname*{sp}(\theta)\leq H$ for all $\theta\in\Theta_{H}$. In Section 4, we consider a finite subset $\Theta\subseteq\Theta_{H}$ of POMDPs. In Section 5, the general class $\Theta=\Theta_{H}$ is considered.

We propose a general Posterior Sampling Reinforcement Learning for POMDPs (PSRL-POMDP) algorithm (Algorithm 1) for both the finite-parameter and the general case. The algorithm maintains a joint distribution on the unknown parameter $\theta_{*}$ as well as the state $s_{t}$. PSRL-POMDP takes the prior distributions $h$ and $f$ as input. At time $t$, the agent computes the posterior distribution $f_{t}(\cdot)$ on the unknown parameter $\theta_{*}$ as well as the posterior conditional probability mass function (pmf) $h_{t}(\cdot;\theta)$ on the state $s_{t}$ for $\theta\in\Theta$. Upon taking action $a_{t}$ and observing $o_{t+1}$, the posterior distribution at time $t+1$ can be updated by applying the Bayes’ rule as²²2When the parameter set is finite, $\int_{\theta}$ should be replaced with $\sum_{\theta}$.

with the initial condition

Recall that $\tau(h_{t}(\cdot;\theta),a_{t},o_{t+1};\theta)$ is a compact notation for (1). In the special case of perfect observation at time $t$, $h_{t}(s;\theta)=\mathbbm{1}(s_{t}=s)$ for all $\theta\in\Theta$ and $s\in{\mathcal{S}}$. Moreover, the update rule of $f_{t+1}$ reduces to that of fully observable MDPs (see Eq. (4) of Ouyang et al. (2017b)) in the special case of perfect observation at time $t$ and $t+1$.

Let $n_{t}(s,a)=\sum_{\tau=1}^{t-1}\mathbbm{1}(s_{\tau}=s,a_{\tau}=a)$ be the number of visits to state-action $(s,a)$ by time $t$. The number of visits $n_{t}$ plays an important role in learning for MDPs (Jaksch et al., 2010; Ouyang et al., 2017b) and is one of the two criteria to determine the length of the episodes in the TSDE algorithm for MDPs (Ouyang et al., 2017b). However, in POMDPs, $n_{t}$ is not ${\mathcal{F}}_{{(t-1)}+}$-measurable since the states are not observable. Instead, let $\tilde{n}_{t}(s,a):=\mathbb{E}[n_{t}(s,a)|{\mathcal{F}}_{{(t-1)}+}]$, and define the pseudo-count $\tilde{m}_{t}$ as follows:

An example of such a sequence is simply $\tilde{m}_{t}(s,a)=t$ for all state-action pair $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$. This is used in Section 4. Another example is $\tilde{m}_{t}(s,a):=\max\{\tilde{m}_{t-1}(s,a),\lceil\tilde{n}_{t}(s,a)\rceil\}$ with $\tilde{m}_{0}(s,a)=0$ for all $(s,a)\in{\mathcal{S}}\times{\mathcal{A}}$ which is used in Section 5. Here $\lceil\tilde{n}_{t}(s,a)\rceil$ is the smallest integer that is greater than or equal to $\tilde{n}_{t}(s,a)$. By definition, $\tilde{m}_{t}$ is integer-valued and non-decreasing which is essential to bound the number of episodes in the algorithm for the general case (see Lemma 5).

Similar to the TSDE algorithm for fully observable MDPs, PSRL-POMDP algorithm proceeds in episodes. In the beginning of episode $k$, POMDP $\theta_{k}$ is sampled from the posterior distribution $f_{t_{k}}$ where $t_{k}$ denotes the start time of episode $k$. The optimal policy $\pi^{*}(\cdot;\theta_{k})$ is then computed and used during the episode. Note that the input of the policy is $h_{t}(\cdot;\theta_{k})$. The intuition behind such a choice (as opposed to the belief $b_{t}(\cdot):=\int_{\theta}h_{t}(\cdot;\theta)f_{t}(\theta)d\theta$) is that during episode $k$, the agent treats $\theta_{k}$ to be the true POMDP and adopts the optimal policy with respect to it. Consequently, the input to the policy should also be the conditional belief with respect to the sampled $\theta_{k}$.

A key factor in designing posterior sampling based algorithms is the design of episodes. Let $T_{k}$ denote the length of episode $k$. In PSRL-POMDP, a new episode starts if either $t>\texttt{SCHED}(t_{k},T_{k-1})$ or $\tilde{m}_{t}(s,a)>2\tilde{m}_{t_{k}}(s,a)$. In the finite parameter case (Section 4), we consider $\texttt{SCHED}(t_{k},T_{k-1})=2t_{k}$ and $\tilde{m}_{t}(s,a)=t$. With these choices, the two criteria coincide and ensure that the start time and the length of the episodes are deterministic. In Section 5, we use $\texttt{SCHED}(t_{k},T_{k-1})=t_{k}+T_{k-1}$ and $\tilde{m}_{t}(s,a):=\max\{\tilde{m}_{t-1}(s,a),\lceil\tilde{n}_{t}(s,a)\rceil\}$. This guarantees that $T_{k}\leq T_{k-1}+1$ and $\tilde{m}_{t}(s,a)\leq 2\tilde{m}_{t_{k}}(s,a)$. These criteria are previously introduced in the TSDE algorithm (Ouyang et al., 2017b) except that TSDE uses the true count $n_{t}$ rather than $\tilde{m}_{t}$.

In this section, we consider $\Theta\subseteq\Theta_{H}$ such that $|\Theta|<\infty$. When $\Theta$ is finite, the posterior distribution concentrates on the true parameter exponentially fast if the transition kernels are separated enough (see Lemma 1). This allows us to achieve a regret bound of $\mathcal{O}(H\log T)$. Let $o_{1:t},a_{1:t}$ be shorthand for the history of observations $o_{1},\cdots,o_{t}$ and the history of actions $a_{1},\cdots,a_{t}$, respectively. Let $\nu_{\theta}^{o_{1:t},a_{1:t}}(o)$ be the probability of observing $o$ at time $t+1$ if the action history is $a_{1:t}$, the observation history is $o_{1:t}$, and the underlying transition kernel is $\theta$, i.e.,

The distance between $\nu_{\theta}^{o_{1:t},a_{1:t}}$ and $\nu_{\gamma}^{o_{1:t},a_{1:t}}$ is defined by Kullback Leibler (KL-) divergence as follows. For a fixed state-action pair $(s,a)$ and any $\theta,\gamma\in\Theta$, denote by ${\mathcal{K}}(\nu_{\theta}^{o_{1:t},a_{1:t}}\|\nu_{\gamma}^{o_{1:t},a_{1:t}})$, the Kullback Leibler (KL-) divergence between the probability distributions $\nu_{\theta}^{o_{1:t},a_{1:t}}$ and $\nu_{\gamma}^{o_{1:t},a_{1:t}}$ is given by

It can be shown that ${\mathcal{K}}(\nu_{\theta}^{o_{1:t},a_{1:t}}\|\nu_{\gamma}^{o_{1:t},a_{1:t}})\geq 0$ and that equality holds if and only if $\nu_{\theta}^{o_{1:t},a_{1:t}}=\nu_{\gamma}^{o_{1:t},a_{1:t}}$. Thus, KL-divergence can be thought of as a measure of divergence of $\nu_{\gamma}^{o_{1:t},a_{1:t}}$ from $\nu_{\theta}^{o_{1:t},a_{1:t}}$. In this section, we need to assume that the transition kernels in $\Theta$ are distant enough in the following sense.

This assumption is similar to the one used in Kim (2017).

Observe that with $\texttt{SCHED}(t_{k},T_{k-1})=2t_{k}$ and $\tilde{m}_{t}(s,a)=t$, the two stopping criteria in Algorithm 1 coincide and ensure that $T_{k}=2T_{k-1}$ with $T_{0}=1$. In other words, the length of episodes grows exponentially as $T_{k}=2^{k}$.

We now consider the general case, where the parameter set is infinite, and in particular, $\Theta=\Theta_{H}$, an uncountable set. We make the following two technical assumptions on the belief and the transition kernel.

Assumption 3 states that the gap between conditional posterior function for the sampled POMDP $\theta_{k}$ and the true POMDP $\theta_{*}$ decreases with episodes as better approximation of the true POMDP is available. There has been recent work on computation of approximate information states as required in Assumption 3 (Subramanian et al., 2020).

There has been extensive work on estimation of transition dynamics of MDPs, e.g., (Grunewalder et al., 2012). Two examples where Assumptions 3 and 4 hold are:

• •

  Perfect observation. In the case of perfect observation, where $h_{t}(s;\theta)=\mathbbm{1}(s_{t}=s)$, Assumption 3 is clearly satisfied. Moreover, with perfect observation, one can choose $\tilde{m}_{t}(s,a)=n_{t}(s,a)$ and select $\hat{\theta}_{k}(s^{\prime}|s,a)=\frac{n_{t}(s,a,s^{\prime})}{n_{t}(s,a)}$ to satisfy Assumption 4 (Jaksch et al., 2010; Ouyang et al., 2017b). Here $n_{t}(s,a,s^{\prime})$ denotes the number of visits to $s,a$ such that the next state is $s^{\prime}$ before time $t$.

• •

  Finite-parameter case. In the finite-parameter case with the choice of $\tilde{m}_{t}(s,a)=t$ for all state-action pairs $(s,a)$ and $\texttt{SCHED}(t_{k},T_{k-1})=t_{k}+T_{k-1}$ or $\texttt{SCHED}(t_{k},T_{k=1})=2t_{k}$, both of the assumptions are satisfied (see Lemma 1 for details). Note that in this case a more refined analysis is performed in Section 4 to achieve $\mathcal{O}(H\log T)$ regret bound.

Now, we state the main result of this section.

The exact constants are known (see proof and Appendix C.1) though we have hidden the dependence above.