0
$\begingroup$

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", 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).

$\endgroup$
2

1 Answer 1

0
$\begingroup$

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" by Williams and Baird.

$\endgroup$
2
  • $\begingroup$ Thankyou @mikkola for your answer, it really helped. $\endgroup$ Commented Oct 22, 2022 at 7:07
  • $\begingroup$ 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 $\endgroup$
    – Alberto
    Commented Mar 23, 2023 at 12:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .