Answers.Body: <p>There's still some missing link since from what you described above we merely know that <span class="math-container">$v^*$</span> is the unique solution to the BOE with Bellman optimality operator. Whether it is the optimal state value of some existent policy <span class="math-container">$\pi^*$</span> is still unclear, thus we need to show <span class="math-container">$v^∗$</span> is the optimal state value of a constructed policy <span class="math-container">$\pi^*$</span> which is then an optimal policy and may not be unique at all.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-06T10:21:58.550Z
Answers.Text: I understand.. Can I construct policy $\pi^*$ by $$\pi^*(s) = \text{argmax}_a \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} p(s', r|\;\cdot\; , a) \big[ r + \gamma v^*(s') \big]$$
Answers.UserDisplayName: mNugget
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-06T23:11:31.980Z
Answers.Text: @mNugget sounds good to me since the optimal policy here must attain probability 1 for a best action in DP.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-04-06T00:19:10.503Z
Answers.LastActivityDate: 2024-04-06T00:19:10.503Z
Answers.UserDisplayName: cinch
Body: <p>I have been trying to prove existence of an optimal policy for RL. I have proved that the Bellman optimality operator, <span class="math-container">$B: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$</span> given by
  <span class="math-container">$$B(v_\pi)(\; \cdot\; ) = \max_{a \in \mathcal{A}(\; \cdot \;)} \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} p(s', r|\;\cdot\; , a) \big[ r + \gamma v_\pi(s') \big]$$</span>
  Is a contraction under the infinity norm. As per usual <span class="math-container">$\mathcal{S}$</span> and <span class="math-container">$\mathcal{A}$</span> denotes the state and action spaces respectively.</p>
  <p>Here is where I am a bit confused. We know that <span class="math-container">$B$</span> must have a unique fixed point, by Banach fixed point theorem. We also know that if an optimal policy exist its state value, <span class="math-container">$v^*$</span>, must be the unique fixed point, since <span class="math-container">$B(v^*) = v^*$</span>. Is this sufficient to conclude that an optimal policy must existence?</p>
  <p><strong>Edit:</strong>
  Would the following reasoning be correct?
  By the Banach fixed-point theorem, <span class="math-container">$v^*$</span> is unique and the sequence <span class="math-container">$\{v_{\pi_n}\}_{n=0}^\infty$</span> defined by <span class="math-container">$v_{\pi_{n+1}} = B(v_{\pi_{n}})$</span> converges to <span class="math-container">$v^*$</span> for any initial state-value function <span class="math-container">$v_0 \in \mathbb{R}^{|\mathcal{S}|}$</span>. In particular <span class="math-container">$\pi_n \overset{n \to \infty}{\longrightarrow}\pi^*$</span>.</p>
  
Tags: <reinforcement-learning><bellman-equations><bellman-operators>
Title: Proof of existence of optimal policy
UserDisplayName: mNugget
ThreadText: # Proof of existence of optimal policy
  
  (Asked by: username_0 on 2024-04-05)
  
  I have been trying to prove existence of an optimal policy for RL. I have proved that the Bellman optimality operator, $B: \mathbb{R}^{|\mathcal{S}|} \to \mathbb{R}^{|\mathcal{S}|}$ given by
  $$B(v\_\pi)(\; \cdot\; ) = \max\_{a \in \mathcal{A}(\; \cdot \;)} \sum\_{r \in \mathcal{R}} \sum\_{s' \in \mathcal{S}} p(s', r|\;\cdot\; , a) \big[ r + \gamma v\_\pi(s') \big]$$
  Is a contraction under the infinity norm. As per usual $\mathcal{S}$ and $\mathcal{A}$ denotes the state and action spaces respectively.
  
  Here is where I am a bit confused. We know that $B$ must have a unique fixed point, by Banach fixed point theorem. We also know that if an optimal policy exist its state value, $v^\*$, must be the unique fixed point, since $B(v^\*) = v^\*$. Is this sufficient to conclude that an optimal policy must existence?
  
  **Edit:**
  Would the following reasoning be correct?
  By the Banach fixed-point theorem, $v^\*$ is unique and the sequence $\{v\_{\pi\_n}\}\_{n=0}^\infty$ defined by $v\_{\pi\_{n+1}} = B(v\_{\pi\_{n}})$ converges to $v^\*$ for any initial state-value function $v\_0 \in \mathbb{R}^{|\mathcal{S}|}$. In particular $\pi\_n \overset{n \to \infty}{\longrightarrow}\pi^\*$.
  
  **Tags:** reinforcement-learning, bellman-equations, bellman-operators
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-04-06. Score: 2 | Accepted answer
  
  There's still some missing link since from what you described above we merely know that $v^\*$ is the unique solution to the BOE with Bellman optimality operator. Whether it is the optimal state value of some existent policy $\pi^\*$ is still unclear, thus we need to show $v^∗$ is the optimal state value of a constructed policy $\pi^\*$ which is then an optimal policy and may not be unique at all.
  
  > **Comments:**
  > **username_0**: I understand.. Can I construct policy $\pi^*$ by $$\pi^*(s) = \text{argmax}_a \sum_{r \in \mathcal{R}} \sum_{s' \in \mathcal{S}} p(s', r|\;\cdot\; , a) \big[ r + \gamma v^*(s') \big]$$  
  > **username_1**: @mNugget sounds good to me since the optimal policy here must attain probability 1 for a best action in DP.  
  
  ---
  
  