1
$\begingroup$

Typically the definition I see for the $Q$ and value functions is $$ Q^\pi(s_t, a_t) = \mathbb{E}_\tau\left[\sum_{t'=t}^T\gamma^{t'-t}r(s_{t'}, a_{t'})\ |\ s_t, a_t\right] \\ V^\pi(s_t) = \mathbb{E}_\tau\left[\sum_{t'=t}^T\gamma^{t'-t}r(s_{t'}, a_{t'})\ |\ s_t\right] $$ where the expectation is taken over trajectories. If $T = \infty$ (that is, in an infinite time horizon), $Q^\pi(s_t, a_t)$ and $V^\pi(s_t)$ do not depend on time. However, for finite time horizons, it seems like they are time dependent: even if $s_2 = s_3$ are the same state, we can have $V^\pi(s_2)\neq V^\pi(s_3)$.

However, I often see people talking about the value and Q-functions as if they aren't dependent on time, irrespective of the value of $T$. For example, when I was learning about policy evaluation, where we fit a function approximator to the value function, the training data we use is $\{(s_t^i, \hat{V}^\pi(s_t^i))\}$ (sampled from a bunch of roll-outs) - this makes it seem like the timestep $t$ is irrelevant: if $s_2^i = s_3^j$, we're expecting the neural network to map both $s_2^i$ and $s_3^j$ to two different values: $\hat{V}^\pi(s_2^i)$ and $\hat{V}^\pi(s_3^j)$. Obviously a function approximator could just fit to the "average" value, but something still seems awry in its formulation.

As other evidence, I often see people write $V^\pi(s)$ for the value function, even in a finite horizon setting, making no mention of the time parameter. In implementations of Q-learning I've seen, the $Q$ function is represented as a 2d-array, not a 3d-array (meaning it's only dependent on the state and the action, not on a timestep).

Can someone help me wrap my head around my misunderstanding? How is it that we can effectively ignore the time parameter? Is is that for large enough $T$, the problem is effectively infinite horizon (since $\gamma^{t'-t}$ becomes so small)?

$\endgroup$

1 Answer 1

1
$\begingroup$

An important caveat that you might be missing is the distinction between "finite horizon" and "episodic" setting for you RL problems. In episodic setting there is a set of terminal states that end the episode. In that context, there is also the time $T$ of termination - but $T$ is a random variable that varies from episode to episode. Because of that it is also sometimes called "indefinite-horizon" setting.

The continuing and episodic settings can be unified by adding an "absorbing state", that transitions only to itself and returns zero reward. So all the results for infinite time horizon setting are valid for episodic setting (even when $\gamma=1$).

For more details you can check the Sutton and Barto book, sections 3.3 and 3.4, plus there is a discussion in the "remarks" section after the chapter 3.


As for finite-horizon problems, your reservations are exactly correct. $Q(s,a)$ values at $t = T-1$ would be exactly equal to expected rewards. At $t = T-2$ you'll have to perform 1-step lookahead, etc. effectively "unrolling" the Bellman equation for each time slice.

$\endgroup$
5
  • $\begingroup$ Interesting, thanks for clarifying the distinction between finite horizon and episodic! If I understand correctly, most RL problems are episodic in nature, and in this case it's equivalent to the infinite horizon case with an absorbing state, so the Q- and value functions are not dependent on time? I'm still not sure I feel comfortable with the "finite horizon, non-episodic" case - it still seems like the Q- and value functions are time-dependent. Is it that we solve those RL problems using more traditional methods like policy gradient, and only define the Q functions in the episodic case? $\endgroup$ Feb 1 at 16:38
  • $\begingroup$ @user3002473 yes, I've edited the answer. To clearly see that finite horizon problem is time-dependent you just need to look at state values at the one-step-before-horizon time. In this case the value is just the expected reward, since you don't care what happens next. $\endgroup$
    – Kostya
    Feb 1 at 18:53
  • $\begingroup$ awesome, thanks so much! (I basically just wanted a sanity check that I wasn't missing something obvious). One final clarification, can you still use Q-learning methods on finite horizon, non-episodic settings, or does it become cumbersome to implement since it's time dependent? $\endgroup$ Feb 1 at 19:00
  • $\begingroup$ @user3002473 Huh... I wanted to answer "I don't really know", but decided to google a bit, and guess what I've found? arxiv.org/abs/2110.15093 It's recent. $\endgroup$
    – Kostya
    Feb 1 at 19:10
  • $\begingroup$ interesting! I'll have to revisit that once my fundamentals are a bit more up to snuff. Thanks again for all the help! $\endgroup$ Feb 1 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.