Body: <p>I have an MDP <span class="math-container">$M$</span> with transition function <span class="math-container">$p$</span>, states <span class="math-container">$S$</span> and a state <span class="math-container">$s^0 \in S$</span>. <span class="math-container">$s^0$</span> has the property that both the most optimistic trajectory (highest expected reward) and the most pessimistic trajectory (lowest expected reward) starting from <span class="math-container">$s^0$</span> have <span class="math-container">$0$</span> expected discounted return.</p>
  <p>Intuitively, once we enter <span class="math-container">$s^0$</span>, it does not matter what we do, the expected reward in the end is <span class="math-container">$0$</span>.</p>
  <p>I would like to prove that the optimal policy in another MDP, <span class="math-container">$M'$</span>, will also be the optimal policy for <span class="math-container">$M$</span>. <span class="math-container">$M'$</span> is the same as <span class="math-container">$M$</span> except with <span class="math-container">$s^0$</span> as an absorbing state (sink state with output <span class="math-container">$0$</span>).</p>
  <p>I am fairly convinced that this is the case. Loosely speaking, I would like to show this by computing the expected return of a policy in both <span class="math-container">$M$</span> and <span class="math-container">$M'$</span>, and showing that they are equal. Ideally, I would compute the expected return of a policy <span class="math-container">$\pi$</span> in both <span class="math-container">$M$</span> and <span class="math-container">$M'$</span>, by multiplying the probability of each trajectory with the value of the rewards along it, and taking a sum over all trajectories.</p>
  <p>Intuitively, if <span class="math-container">$t$</span> is a trajectory in <span class="math-container">$M$</span> induced by <span class="math-container">$\pi$</span>, then <span class="math-container">$t$</span> is also induced in <span class="math-container">$M'$</span> &quot;with the same probability&quot;, and they have the same discounted return. Of course, many different trajectories in <span class="math-container">$M$</span> may map to a single trajectory in <span class="math-container">$M'$</span>, as <span class="math-container">$M'$</span> has <span class="math-container">$s^0$</span> as an absorbing state. However, once we enter <span class="math-container">$s^0$</span> in either MDP, the expected return that follows is <span class="math-container">$0$</span> for any policy in both MDPs (in <span class="math-container">$M$</span>, because of the property of <span class="math-container">$s^0$</span> that bounds returns following it with <span class="math-container">$0$</span> from above and below, and in <span class="math-container">$M'$</span> by definition).</p>
  <p>My immediate difficulty is that there are infinitely many trajectories, and it makes no sense to speak of a &quot;probability of a trajectory&quot;.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-26T21:23:00.853Z
Comments.Text: I am not sure what structuring any sum of rewards in M as a formal structure would help with, since you would write it out formally, then refer to the special constraints and say it was equal to zero. Not sure what you expect to gain by constructing the formula?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-27T10:05:01.340Z
Comments.Text: can't you just replace the MDP connected to $s_0$ with just a self loop?
Comments.UserDisplayName: Alberto
Tags: <reinforcement-learning><markov-decision-process>
Title: How can I prove that early termination in an MDP state is valid?
UserDisplayName: corazza
ThreadText: # How can I prove that early termination in an MDP state is valid?
  
  (Asked by: username_0 on 2023-10-26)
  
  I have an MDP $M$ with transition function $p$, states $S$ and a state $s^0 \in S$. $s^0$ has the property that both the most optimistic trajectory (highest expected reward) and the most pessimistic trajectory (lowest expected reward) starting from $s^0$ have $0$ expected discounted return.
  
  Intuitively, once we enter $s^0$, it does not matter what we do, the expected reward in the end is $0$.
  
  I would like to prove that the optimal policy in another MDP, $M'$, will also be the optimal policy for $M$. $M'$ is the same as $M$ except with $s^0$ as an absorbing state (sink state with output $0$).
  
  I am fairly convinced that this is the case. Loosely speaking, I would like to show this by computing the expected return of a policy in both $M$ and $M'$, and showing that they are equal. Ideally, I would compute the expected return of a policy $\pi$ in both $M$ and $M'$, by multiplying the probability of each trajectory with the value of the rewards along it, and taking a sum over all trajectories.
  
  Intuitively, if $t$ is a trajectory in $M$ induced by $\pi$, then $t$ is also induced in $M'$ "with the same probability", and they have the same discounted return. Of course, many different trajectories in $M$ may map to a single trajectory in $M'$, as $M'$ has $s^0$ as an absorbing state. However, once we enter $s^0$ in either MDP, the expected return that follows is $0$ for any policy in both MDPs (in $M$, because of the property of $s^0$ that bounds returns following it with $0$ from above and below, and in $M'$ by definition).
  
  My immediate difficulty is that there are infinitely many trajectories, and it makes no sense to speak of a "probability of a trajectory".
  
  **Tags:** reinforcement-learning, markov-decision-process
  > **Comments:**
  > **username_1**: I am not sure what structuring any sum of rewards in M as a formal structure would help with, since you would write it out formally, then refer to the special constraints and say it was equal to zero. Not sure what you expect to gain by constructing the formula?  
  > **username_2**: can't you just replace the MDP connected to $s_0$ with just a self loop?  
  
  ---
  
  ## 0 answers
  
  