Proof of [thm:policy gradient].

For any time step \(\hat{t} \in \mathcal{T}\), we can express the return as \[\begin{align} \rho(\pi) &= \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu} \left[ \sum_{t=1}^{T} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \right] \\ &= \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu} \left[ \sum_{t=1}^{\hat{t}-1} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \right] + \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu} \left[ \sum_{t=\hat{t}}^{T} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \right] \\ &\overset{\text{(a)}}{=} C + \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu}\left[ \mathbb{E} \left[ \sum_{t=\hat{t}}^{T} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \mid \tilde{s}_{\hat{t}} , \tilde{m} \right] \right]\\ &\overset{\text{(b)}}{=} C + \sum_{m\in \mathcal{M},s_{\hat{t}}\in \mathcal{S},a_{\hat{t}}\in \mathcal{A}} \mathbb{P}\left[\tilde{m} = m, \tilde{s}_{\hat{t}}= s_{\hat{t}}\right] \pi_{\hat{t}}(s_{\hat{t}}, a_{\hat{t}}) \cdot \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu}\left[ \sum_{t=\hat{t}}^{T} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \mid \tilde{s}_{\hat{t}} = s_{\hat{t}}, \tilde{a}_{\hat{t}} = a_{\hat{t}}, \tilde{m} = m \right]\\ &\overset{\text{(c)}}{=} C + \sum_{m\in \mathcal{M},s_{\hat{t}}\in \mathcal{S},a_{\hat{t}}\in \mathcal{A}} b_{\hat{t},m}^{\pi}(s_{\hat{t}}) \cdot \pi_{\hat{t}}(s_{\hat{t}}, a_{\hat{t}}) \cdot q_{\hat{t},m}^{\pi}(s_{\hat{t}}, a_{\hat{t}})\,. \end{align}\] Here, we use \(C = \mathbb{E}^{\lambda,\pi,p^{\tilde{m}},\mu} \left[ \sum_{t=1}^{\hat{t}-1} r_{t}^{\tilde{m}}(\tilde{s}_{t},\tilde{a}_{t}) \right]\) for brevity. The step (a) follows from the law of total expectation, the step (b) follows from the definition of conditional expectation, and the step (c) holds from the definitions of \(b\) and \(q\) in [eq:v-t-m-s], [eq:backup], and [eq:belief-state].

Using the expression above, we can differentiate the return for each \(s\in \mathcal{S}\) and \(a\in \mathcal{A}\) as \[\frac{\partial \rho(\pi)}{\partial \pi_{\hat{t}}(s,a)} \quad =\quad b_{\hat{t},m}^{\pi}(s) \cdot q_{\hat{t},m}^{\pi}(s, a)\,,\] which uses the fact that \(C\), \(b_{\hat{t},m}^{\pi}\), and \(q_{\hat{t},m}^{\pi}\) are constant with respect to \(\pi_{\hat{t}}\). The desired result then holds by substituting \(t\) for \(\hat{t}\), \(\hat{s}\) for \(s\), and \(\hat{a}\) for \(a\). ◻

Proof of . Assume some iteration \(n\). The proof then follows directly from the contruction of the policy \(\pi^n\) from \(\pi^{n-1}\). By the construction in [eq:swsu-optimal-action], we have that: \[\rho(\pi_1^{n-1}, \dots\pi_{t-1}^{n-1}, \pi_t^n, \pi_{t+1}^{n}\dots, \pi_T^{n}) \; \ge\; \rho(\pi_1^{n-1}, \dots\pi_{t-1}^{n-1}, \pi_t^{n-1}, \pi_{t+1}^{n}\dots, \pi_T^{n})\,.\] Note that the optimal form of the policy in [eq:swsu-optimal-action] follows immediately from the standard first-order optimality criteria over a simplex (e.g, Ex. 3.1.2 in  [1]) and the fact that the function optimized in [eq:swsu-optimal-action] is linear ([cor:ret-linear]). In particular, we have that \[\pi_t^n \in \mathop{\mathrm{argmax}}_{\hat{\pi}_t \in \mathbb{R}^{\mathcal{S} \times\mathcal{A}}}\rho(\pi_1^{n-1}, \dots, \hat{\pi}_t, \dots, \pi_T^{n})\] if and only if for each \(s\in \mathcal{S}\) and \(a\in \mathcal{A}\) \[\frac{\partial \rho(\pi_1^{n-1}, \dots, \pi^n_t, \dots, \pi_T^{n})}{\partial\pi_t(s,\pi_t^n(s))} \; \ge \; \frac{\partial \rho(\pi_1^{n-1}, \dots, \pi^n_t, \dots, \pi_T^{n})}{\partial\pi_t(s,a)}\,.\] Intuitively, this means that the optimal policy \(\pi^n_t\) must choose actions that have the maximum gradient for each state. The optimization in [eq:swsu-optimal-action] then follows by algebraic manipulation from [thm:policy gradient]. ◻

Proof of [thm:no-sublinear-regret]. Consider the MMDP illustrated in 1.

First, we describe the time steps, states, rewards, and actions for this MMDP. This MMDP has three time steps, four states \(\mathcal{S} = \{1,2,3,4 \}\), two actions \(\mathcal{A} = \{1,2\}\), and two models \(\mathcal{M} = \{1,2\}\). The model weight for \(m_{1}\) is \(\lambda\), then the model weight for \(m_{2}\) is \(1-\lambda\). State \(1\) is the only initial state. In model \(m_{1}\), the only non-zero reward 2 is received upon reaching state \(2\). The agent takes action \(1\), which leads to a transition to state \(2\) with a probability of 1. The agent takes action \(2\), which leads to a transition to state \(3\) with probability 1. The agent takes action \(1\) or \(2\) in state \(2\), which leads to a transition to state \(1\) with probability 1. The agent takes action \(1\) or \(2\) in state \(3\), which leads to a transition to state \(1\) with probability 1. The agent takes action \(1\) or \(2\) in state \(4\), which leads to a transition to state \(4\) with probability 1.

In model \(m_{2}\), the agent receives rewards 3 upon reaching state \(4\) and receives rewards 2 upon reaching state \(2\). The agent takes action \(1\), which leads to a transition to state \(2\) with probability 1. The agent takes action \(2\), which leads to a transition to state \(4\) with probability 1. The agent takes action \(1\) or \(2\) in state \(2\), which leads to a transition to state \(1\) with probability 1. The agent takes action \(1\) or \(2\) in state \(4\), which leads to a transition to state \(1\) with probability 1. The agent takes action \(1\) or \(2\) in state \(3\), which leads to a transition to state \(3\) with probability 1.

Now, let us analyze the regret of this MMDP. The optimal policy of the above example is a history-dependent policy. That is, to take action \(2\) at time step \(1\). At time step \(2\), the agent takes action \(1\) or \(2\), which leads to a transaction back to state \(1\). From time step \(3\), if the agent is in model \(m_{1}\), then take action \(1\); if the agent is in model \(m_{2}\), then take action \(2\).

Next, let us analyze the regret of a Markov policy for the MMDP. \(S_{t}\) represents a state at time step \(t\). State \(1\) has two options: select action \(1\) or select action \(2\). If action \(1\) is selected, this will give a regret value of 0 in model \(1\) and a regret value of \(1\) in model \(2\). If action \(2\) is selected, this will give a regret value of \(2\) in model \(1\) and a regret value of \(0\) in model \(2\). Therefore, at time step \(1\), the total regret is 2\(\lambda\) or 1\((1-\lambda\)). At time step \(2\), the agent takes action \(1\) or \(2\) in state \(S_{2}\)(1,3 or 4), which leads to a transition back to state \(1\), and gets zero rewards and zero regrets. Then repeat the procedure. At time step \(3\), the agent can take action \(1\) or action \(2\) in state \(1\) again. For \(T=3\), the trajectory of a Markov policy can be \((S_{1} =1, A_{1} = 1, S_{2},A_{2}, S_{3} =1,A_{3} =1)\), \((S_{1} =1, A_{1} = 1, S_{2},A_{2}, S_{3} =1,A_{3} =0)\), \((S_{1} =1, A_{1} = 0, S_{2},A_{2}, S_{3} =1,A_{3} =1)\), or \((S_{1} =1, A_{1} = 0, S_{2},A_{2}, S_{3} =1,A_{3} =0)\). The accumulated regret can be 2\(\lambda\) +1\((1-\lambda\)), 2\(\lambda\) + 2\(\lambda\), 1\((1-\lambda\)) + 1\((1-\lambda\)). That is, the regret is increased by 1\((1-\lambda\)) or 2\(\lambda\) for every two time steps. \[R_t(\pi) \geq \frac{\min \{2\lambda, 1-\lambda\}}{2} \cdot t\] Let \(c = \frac{\min \{2\lambda, 1-\lambda\}}{2}\), \(t' \geq 2\), then we always have \[R_t(\pi) \geq c \cdot t \quad \text{for all} \quad t \geq t'\;\]

No matter which Markovian policy the agent follows, the accumulated regret will be linear with respect to \(t\). Therefore, for this MMDP, there exists no Markovian policy that achieves sub-linear regret. ◻