Would Deep Q Learning work for a finite horizon problem?

Question

I want to apply Deep Q Learning to a problem, which has a clear finite horizon definition, like:

$$V(s) = \mathbb{E}[r_1 + r_2]$$

Since the horizon is finite, I do not use reward discounting. My action spaces at the time steps 1 and 2 do change and also the policies are therefore clearly not stationary as well. But the state and reward transitions are deterministic as: $r_i(s_i,a_i)$ and $s_{i+1}(s_i,a_i)$. The state space is also very large, so tabular methods are out of question. So the value function can be defined as:

$$V(s) = \sum_{a_1}\sum_{a_2}\left(r_1 + r_2\right)\pi_1(a_1|s_1=s)\pi_2(a_2|s_2(s_1=s,a_1))$$

since the only randomness comes from the policy distributions. (I dropped the reward functions' depedency on the states and actions for clarity). My question is, would Deep Q Learning work for such a finite horizon case? I plan to use two separate MLPs for the Q functions at time steps 1 and 2. I know that the Bellman Optimality can be shown both for the finite and infinite cases; in the finite case, it does not even need the stationarity of the distributions. But all examples on DQNs I came accross during my research solves problems with the infitine horizon assumption. So I just wanted ask for some insight there.

Answer 1

DQN solves optimal control problems for maximising average reward. Although it typically uses discounted reward, the discount factor is not part of the setting - instead it is part of the solution hyperparameters, and usually set quite high e.g. 0.99 - when using function approximators.

The TD target used in DQN is a problem for you:

$$G_{t:t+1} = R_{t+1} + \gamma \text{max}_{a'}Q(S_{t+1},a')$$

as it relies on a Bellman equation that no longer holds for the given value functions. In your case, there does not seem to be any way to express the TD target for time $t$ by referencing other Q values, as you would need to then subtract future rewards, which is very ungainly. Instead, you could use a simple truncated Monte Carlo return

$$G_{t:t+3} = R_{t+1} + R_{t+2} + R_{t+3}$$

There are a few different ways you could do this, but the simplest and closest to DQN would IMO be to:

• Store trajectories in order in the experience replay table
• For each item in the training mini-batch:
  • Pick a start state/action pair to assess $s_t, a_t$ randomly from replay table
  • Check that $a_{t+1}$ and $a_{t+2}$ are maximising actions in your current target policy for $s_{t+1}$ and $s_{t+2}$, reject the sample if not (note you don't need to check or reject $a_t$, and that is how your code learns about exploratory actions)
  • Calculate the TD target, $g_t = r_{t+1} + r_{t+2} + r_{t+3}$
  • Your training data for that example is $s_t, a_t, g_t$

The checking for maximising action parts could be quite slow, so you might prefer to simplify the approach and not use off-policy. Alternatively, if $epsilon$ is low enough you could just store the three step returns directly in the experience replay table (wait until you have the data from $t+3$ before storing data for $t$) and ignore the fact that some returns are from exploratory actions, thus noisy/biased . . . this approach is used in n-step returns in DQN "Rainbow" version and works well enough in practice on the Atari problems despite being on shaky theoretical ground.

---

Note I am using the convention $s_t, a_t, r_{t+1}, s_{t+1}$ to represent a step in the trajectory, whilst in the question you appear to be using $s_t, a_t, r_t, s_{t+1}$ with a different reward index. You will need to convert back if you want to stick with your convention.