I'm reading Chapter 6 of Puterman's MDP :Discrete Stocastic Dynamic Prorgamming. In the book, Bellman operator $\mathscr{L}$ is given as \begin{equation} (\mathscr{L}v)(s) = \sup_{d}\{r_d(s) + \lambda P_d v(s)\},\quad s\in S, v\in\mathbb{R}^S, \end{equation} where $r_d(s)$ is expected immdiate return $r(s,a)$ following the policy $d$ given the state $s$, $P_d$ is the trasition matrix corresponding to $d$, and $0\leq\lambda<1$ is the discounted rate. The supremum is taken over all possible policies d.

Then, (b) of the theorem 6.2.2 states that if $v\leq\mathscr{L}v$, then $v\leq v^{*}_\lambda$, where $v^{*}_\lambda$ is defined by \begin{equation*} v^{*}_\lambda = \sup_{\pi}v^{\pi}_\lambda(s). \end{equation*} Here, $v^{\pi}_\lambda(s)$ is the value following policy $\pi$ with the initial state $s$.

The proof proceeds as follows: if $v\leq \mathscr{L}v$, then for any $\epsilon>0$, there exists some $d$ such that $v\leq r_d + \lambda P_d v + \epsilon e$, where we denote $(1, 1,\cdots)^{\top}$ by $e$, and the inequality applies for each $s$. Then, after playing with some definitions and inequalities, the proof ends.

What makes me confused is, however, taking such $d$ depends on each state $s$, so taking such a universal $d$ seems inappropriate. My question is

Am I missing something, or does the proof have a flaw?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.