Answers.Body: <p>I am assuming you are interested in the case where the objective function is the expected sum of discounted rewards. I realize this answer is probably not directly applicable in the RL context, but might be helpful nevertheless.</p>
  <p>In a finite horizon MDP, an optimal action in a particular state depends not only on the state, but also on the time remaining until the end of the horizon. If there are a lot of decisions remaining after the current one, it makes sense to consider the long-term effects of the current decision. Conversely, if the current decision is the last one, maximizing the immediate reward is all one cares about. Therefore, the solution of a finite horizon MDP with horizon <span class="math-container">$T$</span> is a sequence <span class="math-container">$(\pi_T, \pi_{T-1}, \ldots, \pi_1)$</span> of policies, where a policy <span class="math-container">$\pi_t:S \to A$</span> maps the state to the action when <span class="math-container">$t$</span> decisions remain until the end of the horizon.</p>
  <p>In an infinite horizon MDP, there is always an infinite number of decisions remaining. Informally, this is why a solution of an infinite horizon MDP is a stationary policy <span class="math-container">$\pi: S \to A$</span> that is used regardless of the time step.</p>
  <p>It is a well known strategy to approximate infinite horizon problems by solving a finite horizon MDP with some horizon <span class="math-container">$t$</span>, and then applying <span class="math-container">$\pi_t$</span> at every step in place of <span class="math-container">$\pi$</span> in the infinite horizon problem. To determine what <span class="math-container">$t$</span> needs to be in order to guarantee a certain approximation quality, we can consider the Bellman error
  <span class="math-container">$$
  \epsilon = \sup_s |V_t(s) - V_{t-1}(s)| \stackrel{def.}{=} ||V_t - V_{t-1}||
  $$</span>
  which gives the greatest difference in absolute value between the successive value functions <span class="math-container">$V_t$</span> and <span class="math-container">$V_{t-1}$</span> obtained during value iteration. Now, if we denote the optimal value function of the infinite horizon MDP by <span class="math-container">$V^*$</span>, we can prove
  <span class="math-container">\begin{equation}
  ||V_t - V^*|| \leq \frac{\gamma \epsilon}{1-\gamma}
  \end{equation}</span>
  where <span class="math-container">$\gamma$</span> is the discount factor. Now we can infer that if we want to approximate <span class="math-container">$V^*$</span> with precision of at least <span class="math-container">$\delta$</span>, the Bellman error should satisfy <span class="math-container">$\epsilon &lt; \frac{\delta(1-\gamma)}{\gamma}$</span>.</p>
  <p>We can finally conclude that a possible method of approximating an infinite horizon MDP with a finite horizon MDP with an approximation quality of at least <span class="math-container">$\delta$</span> (in terms of the Bellman error) is to compute by value iteration a sequence <span class="math-container">$V_1, \ldots, V_t$</span> of value functions until we reach a <span class="math-container">$t$</span> where the condition above is satisfied, and then apply the corresponding policy <span class="math-container">$\pi_t$</span>  in the infinite horizon MDP.</p>
  <p>A proof of these facts can be found, e.g., in the <a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3281&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">technical report &quot;Tight performance bounds on greedy policies based on imperfect value functions&quot;</a> by Williams and Baird.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-22T07:07:37.453Z
Answers.Text: Thankyou @mikkola for your answer, it really helped.
Answers.UserDisplayName: Engr. Moiz Ahmad
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-03-23T12:41:10.037Z
Answers.Text: great answer, but that's valid for RL, what about deep RL? at that point, usually bootstrap is used to update the network, however in the POMDP setting you need a belief, thus is the infinite horizon you have no idea when to apply gradient, because truncating it at timestep $t$ might avoid the NN to learn long term dependency
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-04T11:05:20.180Z
Answers.LastActivityDate: 2022-10-04T11:05:20.180Z
Answers.UserDisplayName: mikkola
Body: <p>For a given value of &quot;discount factor&quot; (and reward values' range) in fixed finite horizon markov decision process (MDP), upto how many episodes we have to extend this MDP so that we can approximate the corresponding infinite horizon MDP?</p>
  <p>I am actually working on a research project in which risk-averse MDP (RA-MDP) (with dynamic risk measures) are used which is by nature infinite horizon (<em>this sentence may be irrelevant to answering the question, but I give it as a motivation and to make context</em>). I want to solve this by using online optimization. For this, I am using risk averse actor-critic algorithm, as proposed by Coache et. al. in &quot;<a href="https://arxiv.org/pdf/2206.14666.pdf" rel="nofollow noreferrer">Conditionally elicitable dynamic risk measures for deep reinforcement learning</a>&quot;, which is the latest and the only RL algorithmic framework for risk-averse MDPs, but unfortunately restricted to finite MDPs.  On the other hand, my problem is infinite horizon. So I want to approximate this &quot;infinite horizon&quot; with &quot;finite horizon&quot; case.</p>
  <p>Please help me if you can in this regard (authentic references are appreciable).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-10-02T22:12:58.853Z
Comments.Text: A few suggestions: https://arxiv.org/abs/2110.11383  https://journals.scholarsportal.info/details/00223239/v153i0003/688_aoaawfafcmdp.xml  https://github.com/chauncygu/Safe-Reinforcement-Learning-Baselines
Comments.UserDisplayName: Rob
Tags: <reinforcement-learning><reference-request><markov-decision-process><risk-management>
Title: How can we approximate infinite horizon MDP with finite horizon MDP in the context of reinforcement learning?
UserDisplayName: Engr. Moiz Ahmad
ThreadText: # How can we approximate infinite horizon MDP with finite horizon MDP in the context of reinforcement learning?
  
  (Asked by: username_0 on 2022-10-02)
  
  For a given value of "discount factor" (and reward values' range) in fixed finite horizon markov decision process (MDP), upto how many episodes we have to extend this MDP so that we can approximate the corresponding infinite horizon MDP?
  
  I am actually working on a research project in which risk-averse MDP (RA-MDP) (with dynamic risk measures) are used which is by nature infinite horizon (*this sentence may be irrelevant to answering the question, but I give it as a motivation and to make context*). I want to solve this by using online optimization. For this, I am using risk averse actor-critic algorithm, as proposed by Coache et. al. in "[Conditionally elicitable dynamic risk measures for deep reinforcement learning](https://arxiv.org/pdf/2206.14666.pdf)", which is the latest and the only RL algorithmic framework for risk-averse MDPs, but unfortunately restricted to finite MDPs. On the other hand, my problem is infinite horizon. So I want to approximate this "infinite horizon" with "finite horizon" case.
  
  Please help me if you can in this regard (authentic references are appreciable).
  
  **Tags:** reinforcement-learning, reference-request, markov-decision-process, risk-management
  
  > **Comments:**
  > **username_1**: A few suggestions: https://arxiv.org/abs/2110.11383  https://journals.scholarsportal.info/details/00223239/v153i0003/688_aoaawfafcmdp.xml  https://github.com/chauncygu/Safe-Reinforcement-Learning-Baselines  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-10-04. Score: 0 | Accepted answer
  
  I am assuming you are interested in the case where the objective function is the expected sum of discounted rewards. I realize this answer is probably not directly applicable in the RL context, but might be helpful nevertheless.
  
  In a finite horizon MDP, an optimal action in a particular state depends not only on the state, but also on the time remaining until the end of the horizon. If there are a lot of decisions remaining after the current one, it makes sense to consider the long-term effects of the current decision. Conversely, if the current decision is the last one, maximizing the immediate reward is all one cares about. Therefore, the solution of a finite horizon MDP with horizon $T$ is a sequence $(\pi\_T, \pi\_{T-1}, \ldots, \pi\_1)$ of policies, where a policy $\pi\_t:S \to A$ maps the state to the action when $t$ decisions remain until the end of the horizon.
  
  In an infinite horizon MDP, there is always an infinite number of decisions remaining. Informally, this is why a solution of an infinite horizon MDP is a stationary policy $\pi: S \to A$ that is used regardless of the time step.
  
  It is a well known strategy to approximate infinite horizon problems by solving a finite horizon MDP with some horizon $t$, and then applying $\pi\_t$ at every step in place of $\pi$ in the infinite horizon problem. To determine what $t$ needs to be in order to guarantee a certain approximation quality, we can consider the Bellman error
  $$
  \epsilon = \sup\_s |V\_t(s) - V\_{t-1}(s)| \stackrel{def.}{=} ||V\_t - V\_{t-1}||
  $$
  which gives the greatest difference in absolute value between the successive value functions $V\_t$ and $V\_{t-1}$ obtained during value iteration. Now, if we denote the optimal value function of the infinite horizon MDP by $V^\*$, we can prove
  \begin{equation}
  ||V\_t - V^\*|| \leq \frac{\gamma \epsilon}{1-\gamma}
  \end{equation}
  where $\gamma$ is the discount factor. Now we can infer that if we want to approximate $V^\*$ with precision of at least $\delta$, the Bellman error should satisfy $\epsilon < \frac{\delta(1-\gamma)}{\gamma}$.
  
  We can finally conclude that a possible method of approximating an infinite horizon MDP with a finite horizon MDP with an approximation quality of at least $\delta$ (in terms of the Bellman error) is to compute by value iteration a sequence $V\_1, \ldots, V\_t$ of value functions until we reach a $t$ where the condition above is satisfied, and then apply the corresponding policy $\pi\_t$ in the infinite horizon MDP.
  
  A proof of these facts can be found, e.g., in the [technical report "Tight performance bounds on greedy policies based on imperfect value functions"](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3281&rep=rep1&type=pdf) by Williams and Baird.
  
  > **Comments:**
  > **username_0**: Thankyou @username_2 for your answer, it really helped.  
  > **username_3**: great answer, but that's valid for RL, what about deep RL? at that point, usually bootstrap is used to update the network, however in the POMDP setting you need a belief, thus is the infinite horizon you have no idea when to apply gradient, because truncating it at timestep $t$ might avoid the NN to learn long term dependency  
  
  ---
  
  