Answers.Body: <p>Since this is model-based RL you can use policy iteration method of dynamic programming, and since this MDP is very simple you can intuitively guess an optimal policy for your initial iterated policy <span class="math-container">$\pi_0$</span> as <span class="math-container">$\pi_0(a_1|s_1)=1, \pi_0(a_2|s_2)=1$</span>, where <span class="math-container">$a_1$</span> is the switch action and <span class="math-container">$a_2$</span> is the stay action.</p>
  <p>In the first policy evaluation step we need to solve for the Bellman equation of both states:</p>
  <p><span class="math-container">$v_{\pi_0}(s_1)=\sum_a\pi_0(a|s_1)\big[\sum_rp(r|s_1,a_1)r+\gamma \sum_{s'}p(s'|s_1,a_1)v_{\pi_0}(s')\big]=0+0.5(0.2v_{\pi_0}(s_1)+0.8v_{\pi_0}(s_2))$</span></p>
  <p><span class="math-container">$v_{\pi_0}(s_2)=\sum_a\pi_0(a|s_2)\big[\sum_rp(r|s_2,a_2)r+\gamma \sum_{s'}p(s'|s_2,a_2)v_{\pi_0}(s')\big]=1+0.5v_{\pi_0}(s_2)$</span></p>
  <p>This is a simple system of linear equations of 2 variables <span class="math-container">$v_{\pi_0}(s_1),v_{\pi_0}(s_2)$</span>, you can easily check the solutions are <span class="math-container">$v_{\pi_0}(s_1)=\frac{8}{9},v_{\pi_0}(s_2)=2$</span>.</p>
  <p>Then in the first policy improvement step we need to compute action value for each state-action pair:</p>
  <p><span class="math-container">$q_{\pi_0}(s_1,a_1)=\sum_rp(r|s_1,a_1)r+\gamma \sum_{s'}p(s'|s_1,a_1)v_{\pi_0}(s')=0+0.5(0.2v_{\pi_0}(s_1)+0.8v_{\pi_0}(s_2))=\frac{8}{9}$</span></p>
  <p><span class="math-container">$q_{\pi_0}(s_1,a_2)=\sum_rp(r|s_1,a_2)r+\gamma \sum_{s'}p(s'|s_1,a_2)v_{\pi_0}(s')=0+0.5v_{\pi_0}(s_1)=\frac{4}{9}$</span></p>
  <p><span class="math-container">$q_{\pi_0}(s_2,a_1)=\sum_rp(r|s_2,a_1)r+\gamma \sum_{s'}p(s'|s_2,a_1)v_{\pi_0}(s')=0+0.5(0.2v_{\pi_0}(s_2)+0.8v_{\pi_0}(s_1))=\frac{5}{9}$</span></p>
  <p><span class="math-container">$q_{\pi_0}(s_2,a_2)=\sum_rp(r|s_2,a_2)r+\gamma \sum_{s'}p(s'|s_2,a_2)v_{\pi_0}(s')=1+0.5v_{\pi_0}(s_2)=2$</span></p>
  <p>Therefore the improved policy is updated as <span class="math-container">$\pi_1(a_1|s_1)=1,\pi_1(a_2|s_2)=1$</span>, which apparently already converges to <span class="math-container">$\pi_0$</span> initialized in the above first section. So we can conclude an optimal policy for this MDP is <span class="math-container">$\pi^*(a_1|s_1)=1, \pi^*(a_2|s_2)=1$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-07T05:42:48.610Z
Answers.LastActivityDate: 2024-04-07T05:42:48.610Z
Answers.UserDisplayName: cinch
Body: <p>What is the optimal policy for this MDP?</p>
  <p><a href="https://i.sstatic.net/GVrtA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GVrtA.png" alt="enter image description here" /></a></p>
  
Tags: <reinforcement-learning>
Title: What is the optimal policy for this MDP?
UserDisplayName: DSPinfinity
ThreadText: # What is the optimal policy for this MDP?
  
  (Asked by: username_0 on 2024-04-06)
  
  What is the optimal policy for this MDP?
  
  [![enter image description here](https://i.sstatic.net/GVrtA.png)](https://i.sstatic.net/GVrtA.png)
  
  **Tags:** reinforcement-learning
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-04-07. Score: 3 | Accepted answer
  
  Since this is model-based RL you can use policy iteration method of dynamic programming, and since this MDP is very simple you can intuitively guess an optimal policy for your initial iterated policy $\pi\_0$ as $\pi\_0(a\_1|s\_1)=1, \pi\_0(a\_2|s\_2)=1$, where $a\_1$ is the switch action and $a\_2$ is the stay action.
  
  In the first policy evaluation step we need to solve for the Bellman equation of both states:
  
  $v\_{\pi\_0}(s\_1)=\sum\_a\pi\_0(a|s\_1)\big[\sum\_rp(r|s\_1,a\_1)r+\gamma \sum\_{s'}p(s'|s\_1,a\_1)v\_{\pi\_0}(s')\big]=0+0.5(0.2v\_{\pi\_0}(s\_1)+0.8v\_{\pi\_0}(s\_2))$
  
  $v\_{\pi\_0}(s\_2)=\sum\_a\pi\_0(a|s\_2)\big[\sum\_rp(r|s\_2,a\_2)r+\gamma \sum\_{s'}p(s'|s\_2,a\_2)v\_{\pi\_0}(s')\big]=1+0.5v\_{\pi\_0}(s\_2)$
  
  This is a simple system of linear equations of 2 variables $v\_{\pi\_0}(s\_1),v\_{\pi\_0}(s\_2)$, you can easily check the solutions are $v\_{\pi\_0}(s\_1)=\frac{8}{9},v\_{\pi\_0}(s\_2)=2$.
  
  Then in the first policy improvement step we need to compute action value for each state-action pair:
  
  $q\_{\pi\_0}(s\_1,a\_1)=\sum\_rp(r|s\_1,a\_1)r+\gamma \sum\_{s'}p(s'|s\_1,a\_1)v\_{\pi\_0}(s')=0+0.5(0.2v\_{\pi\_0}(s\_1)+0.8v\_{\pi\_0}(s\_2))=\frac{8}{9}$
  
  $q\_{\pi\_0}(s\_1,a\_2)=\sum\_rp(r|s\_1,a\_2)r+\gamma \sum\_{s'}p(s'|s\_1,a\_2)v\_{\pi\_0}(s')=0+0.5v\_{\pi\_0}(s\_1)=\frac{4}{9}$
  
  $q\_{\pi\_0}(s\_2,a\_1)=\sum\_rp(r|s\_2,a\_1)r+\gamma \sum\_{s'}p(s'|s\_2,a\_1)v\_{\pi\_0}(s')=0+0.5(0.2v\_{\pi\_0}(s\_2)+0.8v\_{\pi\_0}(s\_1))=\frac{5}{9}$
  
  $q\_{\pi\_0}(s\_2,a\_2)=\sum\_rp(r|s\_2,a\_2)r+\gamma \sum\_{s'}p(s'|s\_2,a\_2)v\_{\pi\_0}(s')=1+0.5v\_{\pi\_0}(s\_2)=2$
  
  Therefore the improved policy is updated as $\pi\_1(a\_1|s\_1)=1,\pi\_1(a\_2|s\_2)=1$, which apparently already converges to $\pi\_0$ initialized in the above first section. So we can conclude an optimal policy for this MDP is $\pi^\*(a\_1|s\_1)=1, \pi^\*(a\_2|s\_2)=1$.
  
  
  ---
  
  