34  Designer’s Approach

Author

Affiliation

Aditya Mahajan

McGill University

In all the discussion so far, we have always made an implicit assumption: the decision maker has perfect recall, i.e., it remembers everything that it has seen and done in the past. This assumption, is at the heart of the dynamic programming argument. For example, consider policy evaluation for a POMDP (using standard notation). The value function is given by $$\begin{array}{rl}{V}_t^{\pi }(h_t)& ={\mathbb{E}}^{\pi }[c(S_t,A_t)+\sum _{\tau =t+1}^{T}c(S_{\tau },A_{\tau })|H_t=h_t]\\ & \stackrel{(a)}{=}{\mathbb{E}}^{\pi }[c(S_t,A_t)+{\mathbb{E}}^{\pi }[\sum _{\tau =t+1}^{T}c(S_{\tau },A_{\tau })|H_{t+1}]|H_t=h_t]\\ & ={\mathbb{E}}^{\pi }[c(S_t,A_t)+V_{t+1}^{\pi }(H_{t+1})|H_t=h_t]\end{array}$$ where step $(a)$ relies on the smoothing property of conditional expectation, which only works if the information at time $t+1$ is a superset of the information at time $t$, i.e., the agent has perfect recall.

In this section, we start with the simplest model without perfect recall: a POMDP where actions are chosen based on just the current observation. How do we find the best policy? To avoid any confusion, let’s start with a formal description of the system model.

We assume that the system has a state $S_t\in \mathcal{S}$, control input $A_t\in \mathcal{A}$, and a process noise $W_t\in \mathcal{W}$. The state evolves as $$\begin{array}{}\text{(1)}& S_{t+1}=f_t(S_t,A_t,W_t).\end{array}$$ The observation $Y_t\in \mathcal{Y}$ of the decision maker at time $t$ is given by $$\begin{array}{}\text{(2)}& Y_t={\ell }_t(S_t,N_t)\end{array}$$ where $N_t\in \mathcal{N}$ is the observation noise. As for MPDs and POMDPs, we assume that the primitive random variables $(S_1,W_1,\dots ,W_T,N_1,\dots ,N_T)$ are defined on a common probability space and are mutually independent.

Unlike MDPs and standard POMDPs, it is assumed that the decision maker does not have access to past observations and actions and can choose the current action as a function of just the current observation, i.e., $$A_t={\pi }_t(Y_t)$$ At each time, the system incurs a cost $c_t(S_t,A_t)$ which depends on the current state and the current action. The system operates for a finite horizon $T$ and incurs a total cost $$\sum _{t=1}^T{c}_t(S_t,A_t).$$

Given the above system model, we want to choose a control strategy $\pi =({\pi }_1,\dots ,{\pi }_T)$ to minimize the expected total cost $$J(\pi ):=\mathbb{E}[\sum _{t=1}^T{c}_t(S_t,A_t)].$$ How should we proceed?

Note that the only difference from the POMDP model is that $A_t$ is a function of $Y_t$ rather than $(Y_{1:t},A_{1:t-1})$. Apart from this, the other modeling assumptions are the same. However, the lack of perfect recall implies that the entire machinery of dynamic programming, as presented for MDPs and POMDPs, cannot be applied directly.

An advantage of not having perfect recall is that the size of decision rule ${\pi }_t$ is not increasing with time. Therefore, the number of possible policies is only exponential in $T$ (rather than double exponential, as was the case for POMDPs). Nevertheless, a brute force search is still impractical and we want to find something similar to dynamic programming where the search complexity is linear in time horizon $T$.

34.1 The designer’s approach

The standard “dynamic-progarmming viewpoint” is to evaluate the value function (or the cost-to-go function) from the point of view of the agent at each time. Instead, consider the problem from the point of view of the system designer before the system starts operating. The system designer knows the system model and the statistics of the primitive random variables but does not know the observation of the agent. The designer is concerned with the optimal decision rule for the agent before the system starts operating.

The designer may view the system as a stochastic input-output system: the stochastic inputs are the primitive random variables, the control inputs are the decision rules, and the output is the instantenous cost. The input-output relationship can be described consistently by $(S_t,Y_t)$, which represents the state of the environment and the state of the agent.¹ However, this state cannot be used for optimization because it is not observed by the system designer. So, the optimization problem at the system designer is conceptually equivalent to a POMDP.

¹ In this particular example, we could have worked with just $S_t$ as the state sufficient for input-output mapping, but we carry the “state of the agent” so that the same approach continues to work for more general models.

Hence the designer can obtain a sequential decomposition by forming a belief on the state (sufficient for input-output mapping) of the system, based on all the history of observations and actions available to it (i.e., all the past decision rules, since the designer doesn’t observe anything else). This belief can be described by $$b_t=\mathbb{P}(S_t,Y_t\mid {\pi }_{1:t-1}),$$ which is the “conditional probabilty law” of the “state” conditioned on all the past observations and “control actions” of the designer. Technically, $b_t$ is not a conditional probability law, rather it is unconditional probability law; but this fact is a techinicality which does not affect the solution methodology.

The belief state sastisfies the usual properties of an information state.

Lemma 34.1 The belief state satisfies the following properties.

1. Sufficient for predicting itself. There exists a linear transformation $H_t({\pi }_t)$ such that $$b_{t+1}=H_t({\pi }_t)b_t.$$

2. Sufficient for performance evaluation. There exists functions ${\overline{c}}_t:[\mathcal{S}\to \mathcal{A}]\to \mathbb{R}$ such that the expected per-step cost can be expressed as $$\mathbb{E}[c_t(S_t,A_t)\mid {\pi }_{1:t}]={\overline{c}}_t(b_t,{\pi }_t).$$

Proof

Since the “belief” is an unconditional probability, it evolves similar to the probability distribution of a Markov chain. In particular, :$$\begin{array}{rl}{b}_{t+1}(s_{t+1},y_{t+1})& =\mathbb{P}(s_{t+1},y_{t+1}\mid {\pi }_{1:t})\\ & =\mathbb{P}(y_{t+1}\mid s_{t+1})\sum _{\begin{array}{c}{s}_t\in \mathcal{S}\\ y_t\in \mathcal{Y}\end{array}}\mathbb{P}(y_t\mid s_t)\mathbb{P}(s_{t+1}\mid S_t=s_t,A_t={\pi }_t(y_t))\mathbb{P}(s_t\mid {\pi }_{1:t-1})\\ & =:[H_t({\pi }_t)b_t](s_{t+1},y_{t+1}).\end{array}$$ This proves the first part of the result. Note that the transformation $H_t({\pi }_t)$ is linear in the sense that for any belief $b_t$ given as a linear combination of two beliefs $b_t^{(1)}$ and $b_t^{(2)}$, i.e., $$b_t=\lambda b_t^{(1)}+(1-\lambda )b_t^{(2)}$$ we have $$H_t({\pi }_t)b_t=\lambda H_t({\pi }_t)b_t^{(1)}+(1-\lambda )H_t({\pi }_t)b_t^{(2)}.$$

For the second part, note that $$\begin{array}{rl}\mathbb{E}[c_t(S_t,A_t)\mid {\pi }_{1:t}]& =\sum _{s_t\in \mathcal{S}}{c}_t(s_t,{\pi }_t(s_t))\mathbb{P}(s_t\mid {\pi }_{1:t-1})\\ & =:{\overline{c}}_t(b_t,{\pi }_t).\end{array}$$ This proves the second part of the result.

The decision rule ${\psi }_t:b_t\mapsto {\pi }_t$ followed by the designer is called a meta-policy (to distinguish it from the policy of the agent). The optimal meta-policy $\psi =({\psi }_1,\dots ,{\psi }_T)$ can be obtained by solving the following dynamic program.

Dynamic program

Initialize $V_{T+1}(b)\equiv 0$. Then, for all $t\in \{T,\dots ,1\}$, recursively define: $$\begin{array}{rl}{Q}_t(b,\pi )& ={\overline{c}}_t(b,\pi )+V_{t+1}(H_t(\pi )b)\\ V_t(b)& =\underset{\pi \in \mathrm{\Pi }}{min}{Q}_t(b,\pi )\end{array}$$

Let ${\psi }_t(b)$ denote the arg min of $Q_t(b,\pi )$. Then, the meta-strategy $\psi =({\psi }_1,\dots ,{\psi }_T)$ is optimal.

Some properties of the solution

1. The set $\mathrm{\Pi }$ above may be restricted to all deterministic maps from $\mathcal{S}$ to $\mathcal{A}$ without any loss of optimality.

2. As for POMDPs, we can show that the value function $V_t$ is piecewise linear and convex.

How to determine the policy?

The dynamic program above determines a meta-policy $\psi$. The corresponding policy $\pi =({\pi }_1,\dots ,{\pi }_T)$ may be determined as follows.

• Start with the initial belief $b_1$ (which is the same as the initial distribution of the state $S_1$). Choose ${\pi }_1={\psi }_1(b_1)$.
• Let $b_2=H_1({\pi }_1)b_1$. Choose ${\pi }_2={\psi }_2(b_2)$.
• Let $b_3=H_2({\pi }_2)b_2$. Choose ${\pi }_3={\psi }_3(b_3)$.
• …

Optimal policies for infinite horizon are not time-homogeneous

Although we presented the result for the finite-horizon setting, the argument naturally extends to the infinite horizon setting as well. In particular, consider the infinite horizon discounted cost setting. Then, the optimal meta-policy is given by the unique bounded fixed point of the following equation: $$V(b)=\underset{\pi \in \mathrm{\Pi }}{min}\{\overline{c}(b,\pi )+\gamma V(H(\pi )b)\},\mathrm{\forall }b\in \mathrm{\Delta }(\mathcal{S}\times \mathcal{Y}).$$ This implies that the meta-policy $\psi$ is time-homogeneous but the policy $\pi =({\pi }_1,{\pi }_2,\dots )$ (chosen according to the procedure described above) is not time-homogeneous.

34.2 The general idea

Now we generalize the discussion above to a general multi-agent control problem. Suppose that the system has a state $S_t\in \mathcal{S}$. There are $N$ controllers, indexed by the set $\mathcal{N}:=\{1,\dots ,N\}$. Let $Y_t^n\in \mathcal{Y}$ and $A_t^n\in {\mathcal{A}}^n$ denote the observation and action, respectively, of agent $n\in \mathcal{N}$ at time $t$. We assume that the observations are given by $$Y_t^n={\ell }_t^n(S_t,W_t^n),n\in \mathcal{N}$$ and the state evolves as $$S_{t+1}=f_t^0(S_t,A_t,W_t^0)$$ where $A_t$ denotes the vector $(A_t^1,\dots ,A_t^N)$ of all actions. We assume that the noise processes $\{W_t^0{\}}_{t\ge 1}$, $\{W_t^n{\}}_{t\ge 1}$, $n\in \mathcal{N}$, are independent across time and also mutually independent.

We assume that all agents use finite state controllers. In particular, agent $n\in \mathcal{N}$ uses a local state $Z_t^n\in {\mathcal{Z}}^n$. At time $t$, agent $n$ first updates its state using a state-update function $f_t^n$, as follows: $$Z_t^n=f_t^n(Z_{t-1}^n,Y_t^n)$$ and then uses the updated state to choose an action as follows: $$A_t^n={\pi }_t^n(Z_t^n).$$ We call $Z_t^n$ as agent state.

A commonly used example of agent state is $Z_t^n=(Y_{t-d+1}^n,Y_{t-d+2}^n,\dots ,Y_t^n)$ where the agent uses a sliding window of the last $d$ observations as a local state. The example presented in the previous section is a special case of a sliding window controller with window size $d=1$.

Thus, we can view the problem from the time of a view of a system designer. The state sufficient for input-output mapping is $(S_t,Z_t^1,\dots ,Z_t^n)$; the control input is $(f_t^1,\dots ,f_t^n,{\pi }_t^1,\dots ,{\pi }_t^n)$ and the output is the instanteous cost. We separate the belief state before taking actions and the belief state before updating the local memory: $$\begin{array}{rl}{b}_t& =\mathbb{P}(S_t,Z_t^1,\dots ,Z_t^N\mid f_{1:t}^{1:N},{\pi }_{1:t-1}^{1:N}),\\ {\overline{b}}_t& =\mathbb{P}(S_{t+1},Z_t^1,\dots ,Z_t^N\mid f_{1:t}^{1:N},{\pi }_{1:t}^{1:N}).\end{array}$$

As for Lemma 34.1, we can show the following:

Lemma 34.2 The belief state satisfies the following properties.

1. Sufficient for predicting itself. There exists a linear transformations $H_t({\pi }_t^{1:N})$ and ${\overline{H}}_t(f_t^{1:N})$ such that $$\begin{array}{rl}{\overline{b}}_t& =H_t({\pi }_t^{1:N})b_t,\\ b_{t+1}& ={\overline{H}}_t(f_t^{1:N}){\overline{b}}_t.\end{array}$$

2. Sufficient for performance evaluation. There exists functions ${\overline{c}}_t:[\mathcal{S}\to \mathcal{A}]\to \mathbb{R}$ such that the expected per-step cost can be expressed as $$\mathbb{E}[c_t(S_t,A_t)\mid f_{1:t}^{1:N},{\pi }_{1:t}^{1:N}]={\overline{c}}_t(b_t,{\pi }_t^{1:N}).$$

Therefore, we can obtain the following dynamic programming decomposition.

Dynamic program

Initialize $V_{T+1}(b)\equiv 0$. Then, for all $t\in \{T,\dots ,1\}$, recursively define: $$\begin{array}{rl}{Q}_t(b,{\pi }^{1:N})& ={\overline{c}}_t(b,f^{1:N},{\pi }^{1:N})+{\overline{V}}_t(H_t({\pi }^{1:N})b)\\ {\overline{Q}}_t(\overline{b},f^{1:N})& =V_{t+1}({\overline{H}}_t(f^{1:N})\overline{b}),\end{array}$$ and $$\begin{array}{rl}{V}_t(b)& =\underset{{\pi }^{1:N}}{min}{Q}_t(b,{\pi }^{1:N}),\\ {\overline{V}}_t(\overline{b})& =\underset{f^{1:N}}{min}{\overline{Q}}_t(\overline{b},f^{1:N}).\end{array}$$

Let ${\psi }_t(b)$ and ${\overline{\psi }}_t(\overline{b})$ denote the arg min of $Q_t(b,{\pi }^{1:N})$ and ${\overline{Q}}_t(\overline{b},f^{1:N})$. Then, the meta-strategy $({\psi }_1,{\overline{\psi }}_1,{\psi }_2,{\overline{\psi }}_2,\dots ,{\psi }_T)$ is optimal.

Simplifying the dynamic program

Instead of optimizing the dynamic program over all policies $f^{1:N}$ and ${\pi }^{1:N}$ at once, we can optimize them one by one. In particular, define an intermediate beliefs $$\begin{array}{rl}{b}_t^1& =\mathbb{P}(S_t,Z_t^1,\dots Z_t^N,A_t^1\mid f_{1:t}^{1:N},{\pi }_{1:t}^1,{\pi }_{1:t-1}^{2:N}),\\ b_t^2& =\mathbb{P}(S_t,Z_t^1,\dots Z_t^N,A_t^{1:2}\mid f_{1:t}^{1:N},{\pi }_{1:t}^{1:2},{\pi }_{1:t-1}^{3:N}),\\ \cdots & =\cdots \\ b_t^N& =\mathbb{P}(S_t,Z_t^1,\dots Z_t^N,A_t^{1:N}\mid f_{1:t}^{1:N},{\pi }_{1:t}^{1:N}),\end{array}$$ and $$\begin{array}{rl}{\overline{b}}_t^1& =\mathbb{P}(S_{t+1},Z_{t+1}^1,Z_t^{2:N}\mid f_{1:t+1}^1,f_{1:t}^{2:N},{\pi }_{1:t}^{1:N}),\\ {\overline{b}}_t^2& =\mathbb{P}(S_{t+1},Z_{t+1}^{1:2},Z_t^{3:N}\mid f_{1:t+1}^{1:2},f_{1:t}^{3:N},{\pi }_{1:t}^{1:N}),\\ \cdots & =\cdots \\ {\overline{b}}_t^N& =\mathbb{P}(S_{t+1},Z_{t+1}^{1:N}\mid f_{1:t+1}^{1:N}{\pi }_{1:t}^{1:N}).\end{array}$$

Then, we can show that these beliefs update as: $$b_t\stackrel{H_t^1({\pi }_t^1)}{\to }{b}_t^1\stackrel{H_t^2({\pi }_t^2)}{\to }\cdots \stackrel{H_t^N({\pi }_t^N)}{\to }{b}_t^N\to {\overline{b}}_t\stackrel{{\overline{H}}_t^1(f_{t+1}^1)}{\to }{\overline{b}}_t^1\stackrel{{\overline{H}}_t^2(f_{t+1}^2)}{\to }\cdots {\overline{b}}_t^N=b_{t+1}.$$ We can then decompose the DP over time in a similar manner and just optimize over only one of ${\pi }_t^n$ or $f_t^n$ at each step.

Notes

The presentation here is borrowed from Mahajan (2008). The general idea first appeared in Witsenhausen (1973), where it was called the standard form. The model in Witsenhausen (1973) was fairly general. It was specialized to POMDPs with finite memory in Sandell (1974). Witsenhausen’s standard form was rediscovered in Dibangoye et al. (2016), where it was called occupation MDP.

Dibangoye, J.S., Amato, C., Buffet, O., and Charpillet, F. 2016. Optimally solving dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research 55, 443–497. DOI: 10.1613/jair.4623.

Mahajan, A. 2008. Sequential decomposition of sequential dynamic teams: Applications to real-time communication and networked control systems. PhD thesis, University of Michigan, Ann Arbor, MI.

Sandell, J., Nils R. 1974. Control of finite-state, finite-memory stochastic systems. PhD thesis, Massachussets Institute of Technology, Cambridge, MA.

Witsenhausen, H.S. 1973. A standard form for sequential stochastic control. Mathematical Systems Theory 7, 1, 5–11. DOI: 10.1007/bf01824800.