1
$\begingroup$

I'm working through the book Approximate Dynamic Porgramming by Warren B. Powell. Currently I'm solving exercise 3.3 and 3.5. Let me state the exercise (I'm summarizing the text from the boook)

We have the following Markov Decision Problem. We have a two-stage Markov chain with one-step transition matrix $$ P= \begin{pmatrix} 0.7 & 0.3 \\ 0.05 & 0.95 \\ \end{pmatrix} $$ The contribution from each transition from state $i\in\{1,2\}$ to state $j\in\{1,2\} $is given by $$ C = \begin{pmatrix} 10 & 30 \\ 20 & 10 \\ \end{pmatrix} $$

that means going from state $1$ to state $2$ has a contribution (reward) of $30$.

Since the exercise are asking to solve the problem using value iteration (infinite horizon) and policy iteration let me state the two algorithms from the book (again I'm quoting)

Value Iteration

  1. Set the initial value $v^0 = 0 $ for all state $s\in S$, fix a tolerance parameter $\epsilon$ and set $n=1$.
  2. For each state $s$ compute $$ v^n(s) = \max_a (C(s,A) + \gamma\sum_{s'}P(s'|s,a) v^{n-1}(s'))$$
  3. If $\|v^n-v^{n-1}\| <\epsilon(1-\gamma)/2\gamma $ let $ \pi^\epsilon$ be the resulting policy and $v^n$ the resulting value. Else set $n=n+1$ and go to step 2

and the policy iteration (again quoting the book)

Policy Iteration

  1. Select a policy $\pi^0$ and set $n=1$. $\epsilon$ and set $n=1$.
  2. Given the policy $\pi^{n-1}$ compute the transition matrix $P^n$ and the contribution vector $c^n$ where the element for state $s$ is given by $c^{n-1} = C(s, \pi^{n-1})$
  3. let $v^{n-1}$ be the solution to ($I$ the identity matrix) $$(I - \gamma P^n) v = c^{n-1}$$
  4. find a policy $\pi^n$ defined by $$ a^n(s) = \arg\max_a(C(a)+\gamma P^nv^n)$$ this requires to compute the action $a$ for each state $s$.
  5. if $a^n(s)=a^{n-1}(s)$ for all $s$ then stop. Otherwise set $n=n+1$ and go to step $2$.

Now let me state the two exercises. In exercise $3.3$ we need to achieve the following two tasks:

Exercise 3.3 Plot the value of being in state 1 as a function of the number of iterations if your initial estimate of value being in each state is $0$. Show the graph for $100$ iteration. Repeat the exercise with initial estimates of $100$ each and $100$ for state $1$ and $0$ for state. The author says (note that you are not choosing a decision so there is no maximization step)

I've used R to implement the value iteration:

P <- matrix(c(0.7, 0.3, 0.05, 0.95), nrow=2, byrow=T)
C <- matrix(c(10, 30, 20, 5),nrow=2, byrow = T)
discount <- 0.8
v <- matrix(rep(0,200), nrow=100)
for(i in 2:100){
  v[i,] <- (C[1,] + discount*sum(P[1,]*v[i-1,1]))
}

where I've used $P[1, ]$ since we are only interested in the value of being in state $1$. Here are the graphs for the different initial states

both $0$ initial value enter image description here both $100$ initial value enter image description here and $100$ and $0$ initial value enter image description here

FIRST QUESTION is the solution correct? I'm a bit unsure since the last initial value pair did not change the plot compared to the two above ones.

the second exercise is the following

Exercise 3.5 Apply policy iteration to the above problem. Plot the average value function after each iteration alongside the average value function found using value iteration after each iteration (initial value $0$).

With this I'm struggling. It's not really clear to me how to use policy iteration if there is no policy to choose from as the author outlined above.

From the discussion with Kirill in the comments you can see that I've first tried to introduce a policy to solve this exercise which seems to be wrong. However, for completeness I leave the results in the old outdated part below.


OLD OUTDATED PART

Clearly there are policies of the form: being in state $i$ go either to state $j$ or stay at state $i$. We can model this via tuples $(i,j)$ meaning if I'm in state $1$ I go to state $i$ and if I'm in state $2$ I go to state $j$. I've also implemented the algorithm in R. Note that several steps of the above policy iteration are not needed to be recalculated since they are constant. What confuses me is that the author say above there are no decision but now we should solve it via policy iteration. Moreover, my resulting value is different which means something is wrong. Can someone help me to understand what's going wrong.

P <- matrix(c(0.7, 0.3, 0.05, 0.95), nrow=2, byrow=T)
C <- matrix(c(10, 30, 20, 5),nrow=2, byrow = T)
discount <- 0.8
v <- c(0,0)
current_policy = c(1,2)
id <- matrix(c(1,0,0,1), nrow=2, byrow=T)
inverse_factor = solve(id-discount*P)
new_policy = c(1,1)
while(any(new_policy != current_policy)){
  current_policy = new_policy
  c_pi = c(C[1,current_policy[1]],C[2,current_policy[2]])
  current_value = inverse_factor%*%c_pi
  a_1 = which.max(c(C[1,1]+discount*(P%*%current_value)[1],C[1,2]+discount*(P%*%current_value)[2]))
  a_2 = which.max(c(C[2,1]+discount*(P%*%current_value)[1],C[2,2]+discount*(P%*%current_value)[2]))
  new_policy = c(a_1,a_2)
  v <- rbind(v,t(current_value))
}
$\endgroup$
7
  • $\begingroup$ So what exactly is the control, and the objective, in your problem right at the top of the question? Could you write it out more explicitly? You have $P(s'\mid s,a)$ in one place, but only $P(s'\mid s)$ in the problem. Where is $a$? Where is the "max" in your value iteration? $\endgroup$
    – Kirill
    Sep 28 '17 at 18:31
  • $\begingroup$ @Kirill thx for your comment. As I wrote, the author says: "Exercise 3.3 Plot the value of being in state 1 as a function of the number of iterations if your initial estimate of value being in each state is 0. Show the graph for 100 iteration. Repeat the exercise with initial estimates of 100 each and 100 for state 1 and 0 for state. The author says (note that you are not choosing a decision so there is no maximization step)". Note the last sentence in brackets. I wrote down the policy / value iteration for a general problem (involving a decision $a$). $\endgroup$
    – math
    Sep 28 '17 at 18:37
  • $\begingroup$ @Kirill That's the exact sentence he's using: Apply the value iteration for an infinite horizon problem (note that you are not choosing a decision so there is no maximization step). $\endgroup$
    – math
    Sep 28 '17 at 18:39
  • $\begingroup$ Then how can you have a policy when there are no decisions to be made? (A policy is a function of state $\pi(s) = \mathrm{argmax}_{a\in\mathcal{A}}(\cdots)$.) I think the disconnect between the different parts of your question makes your question more confusing and complicated than strictly necessary. $\endgroup$
    – Kirill
    Sep 28 '17 at 18:42
  • $\begingroup$ @Kirill I'm sorry if the question is not clear. How can I improve clarity? In a nutshell the author wants to solve the problem first with value function iteration and then with policy iteration. Regarding missing policy: I do agree that this is very confusing and I tried to point this out in my question. $\endgroup$
    – math
    Sep 28 '17 at 18:47

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.