IIUC, the value function of a state $s$ given a policy $\pi$, $v^{\pi}(s)$, is the expected (discounted) return starting from $s$. The confusing part for me is that if it is possible to revisit a state in an episodic task and each episode has at most $\tau$ time steps, the time that we see a state is relevant. Is there an underlying assumption that the MDP of episodic tasks is a DAG and the maximum number of time steps in an episode $\tau$ is just the length of longest path in the DAG (and not a artificially imposed limit)?
1 Answer
$\begingroup$
$\endgroup$
3
Depending on the notation, $\tau$ either means the length of a particular episode (and so changes between episodes). It would also be valid to have $\tau $ denote the longest possible episode, although I have not seen it used in that way.
Sometimes, $\tau$ can be used as a hard limit on the maximum number of timesteps in an episode. For example, when playing Atari games, it is a common practice to truncate the maximum play time to say 5 minutes, in order to encourage more exploration of the state space.
You are correct that if $\tau$ was used as a cap on the number of time steps then time would have to be incorporated into the state in order for the MDP assumption to hold.
However, in the case of the Atari games and artificial termination, I have not seen the time as part of the state. That is probably because it's such a small violation of the MDP conditions that not much of value is lost.
-
$\begingroup$ In cases that we impose a cap on the number of time steps, the only issue is not that the Markovian property is violated if we do not consider time. Regardless of how small this violation is, it's not clear for me what the definition of a value function is and if the Bellman equations make sense anymore. $\endgroup$ Commented Aug 21, 2017 at 2:04
-
$\begingroup$ Thinking about your answer, one other way to look at this is that in cases with a cap on number time steps, a state includes timestamp and the MDP of RL task is defined on this new state space (which can be easily constructed from the MDP of environment e.g. an Atari game). This new MDP is a DAG (because of time stamps as there is no way to return to a past time). $\endgroup$ Commented Aug 21, 2017 at 2:11
-
$\begingroup$ Yes, you are correct that putting a cap on the time makes the idea of value function a poorly defined concept, and that augmenting the state with the timestamp would fix it. However, in practice, people just run the same RL algorithms without augmenting the timestamp and it works anyway. $\endgroup$– shimaoCommented Aug 21, 2017 at 3:42