3
$\begingroup$

I am modelling a ride-hailing system where passenger requests continuously arrive into the system. An RL model is developed to learn how to match those requests with drivers efficiently.

Basically, the system can run infinitely as long as there are requests arriving (infinite horizon reality). However, in order for the RL training to conduct, the episode length should be restricted to some finite duration, say $[0,T]$ (finite horizon training).

My question is how to implement the learned policy based on finite horizon $[0,T]$ to the real system with infinite horizon $[0,\infty]$?

I expect there would be a conflict of objectives. The value function near $T$ is partially cut off in a finite horizon and would become an underestimate and affect policy performance in an infinite horizon implementation. To this end, I doubt the applicability of the learned policy.

$\endgroup$
2
$\begingroup$

A normal way to deal with training on infinite horizon (aka "continuing" or "non-episodic") problems is to use TD learning or other bootstrapping methods (of which Q-learning in DQN is one example), and to treat the cutoff at $T$ for pseudo-episodes as a training artefact.

If the state at time $T$ was really a terminal state, the TD target would be just $r$ because $q(s^T,\cdot) = 0$ by definition, but that doesn't apply in your case.

So always use the bootstrapped TD target - e.g. $r + \gamma \text{max}_{a'} \hat{q}(s',a',\theta)$ for single step TD target with a Q estimate having $\theta$ as learned params - and don't treat the horizon data any differently.

If you do this, then your concerns about under-estimates should not be an issue. Your pseudo-episodes do need to be long enough to observe the impact of multiple requests in the long term is the main issue (setting $T$ too low so that the system does not reach any kind of equilibrium would be a problem).

You could also use an average reward setting and differential value functions. It is slightly better from a theoretical standpoint, but Q-learning and DQN is fine if you don't want to be bothered with that. The same basic rule applies - ignore "episode end" for constructing TD targets because it is just a training artefact. Also ensure you set $T$ high enough that the long term impacts of a policy are observable.

If your starting state is special (e.g. cars all in fixed places, and no requests in progress) this could also be an issue, because the real world system will rarely be in that state but you will have many episode starts with it. If you cannot start the system in a reasonable random initial state for your problem, you may also want to discard data from episode starts and allow a run-in time before using data for training from the pseudo-episodes.

$\endgroup$
7
  • $\begingroup$ For infinite horizon, i.e. non-episodic tasks, can I use DQN with no episodes, γ=0.99, and only one terminal state that is the timestep limit ? $\endgroup$
    – ddaedalus
    Sep 13 '20 at 13:27
  • 1
    $\begingroup$ @ddaedalus: Yes, sort of, that is what this answer describes. Technically the termination condition is not real or part of the state, so you just use it to trigger a stop to collecting training data and re-set the state for convenience. You should use value function updates as if that last state is not terminal. Because it isn't. $\endgroup$ Sep 13 '20 at 14:54
  • $\begingroup$ Yes, I got it. Thanks a lot. $\endgroup$
    – ddaedalus
    Sep 13 '20 at 14:56
  • $\begingroup$ Awesome point - ignore "episode end" for constructing TD targets because it is just a training artefact. Helping me understand instantly, thanks. Found your solution agrees with this paper I was reading. It is all about time limits that are not regarded terminal states from the perspective of the environment. However, it involves overwriting the agent training processes, kind of tricky since I am using agents from Stable Baselines. Do you have any experience for such a modification? $\endgroup$ Sep 15 '20 at 7:52
  • $\begingroup$ Your remark about the lengh of $T$ is also helpful. However, my system is time-dependent since it is a traffic system, supply and demand are constantly changing and stochastic. which means the system is non-stationary. For a non-stationary system, if I train the agent in $[0, T]$, does it mean the policy is only applicable for $[0, T]$ since the traffic conditions change after $T$? $\endgroup$ Sep 15 '20 at 7:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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