# How to apply Q-learning when rewards is only available at the last state?

I have a scheduling problem in which there are $$n$$ slots and $$m$$ clients. I am trying to solve the problem using Q-learning so I have made the following state-action model.

A state $$s_t$$ is given by the current slot $$t=1,2,\ldots,n$$ and an action $$a_t$$ at slot $$t$$ is given by one client, $$a_t\in\{1,2,\ldots,m\}$$. In my situation, I do not have any reward associated with a state-action pair $$(s_t,a_t)$$ until the terminal state which is the last slot. In other words, for all $$s_t\in\{1,2,\ldots,n-1\}$$, the reward is $$0$$ and for $$s_t=n$$ I can compute the reward given $$(a_1,a_2,\ldots,a_n)$$.

In this situation, the Q table, $$Q(s_t,a_t)$$, will contain only zeros except for the last row in which it will contain the updated reward.

Can I still apply Q-learning in this situation? Why do I need a Q table if I only use the last row?

• Your question is very similar to this one. Given that you provide an example of a specific problem, I will not close it as an exact duplicate. – nbro Jan 24 at 3:38

Having only a non-zero reward at the very end is not uncommon. When rewards are sparse, it becomes a bit harder to learn compared to having lots of different rewards along the way, but for your problem, the goal state is always reached, so that should not be a problem. (The real problem with sparse rewards is that, if an agent can do a lot of exploration without every finding the goal, it essentially receives no feedback and will behave randomly, until it happens to stumble upon the very rare reward state.)

What concerns me more about your problem is that the final reward depends not just on the last state visited, but also on the chain of actions taken so far. That means that, to make this a proper MDP, you need to keep the chain of action in the state. So, your state would be something of the type $$(s_k, [a_1, a_2, \ldots, a_{k-1}])$$.

This kind of combinatorial problem is not what RL is really great at. RL is really good when the state and action together give a lot of information about the next state. Here it seems that, in your formulation, the next state is independent of the previous action.

Instead of seeing this as a RL problem, you might want to express this as sequences of actions with an associated reward, and look at it as a combinatorial optimization problem.

• What OP is describing is, in fact, a combinatorial optimisation problem. Scheduling is a classic CO problem -- I think that it should be solvable using RL, OP would just have to be careful with how he defines an MDP. It is likely that vanilla DQN would be unable to solve his problem though, given all the variables. I think a good approach would be to view it as a POMDP and represent each machine as an agent. – David Ireland Aug 27 '20 at 18:30
• Yeah, that's why I mentioned combinatorial optimization in the last line of my answer. – Robby Goetschalckx Aug 27 '20 at 18:42

If by,

I can compute the reward given $$(a_1, a_2, \dots, a_n)$$

you simply mean that your game is deterministic, this is absolutely fine. I feel another answer had assumed you were implying your terminal reward is a matter of some sequence. RL does, however, struggle more greatly in games with indeterminable reward until the terminal state, however, it is perfectly normal, but a significant challenge.

In terms of implementation, simply record the reward at the end of each match, and perform a train step only after each terminal state, assigning this reward to each transition recorded in that game. Instead of updating your target network after a given number of steps, update it after some number of terminal states. I suggest 20 games as a starter for the frequency of updating your target network.