Answers.Body: <p>If by,</p>
  <blockquote>
  <p>I can compute the reward given <span class="math-container">$(a_1, a_2, \dots, a_n)$</span></p>
  </blockquote>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-27T17:47:51.427Z
Answers.LastActivityDate: 2020-08-27T17:47:51.427Z
Answers.UserDisplayName: user192361237
Answers.Body: <p>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.)</p>
  <p>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 <span class="math-container">$(s_k, [a_1, a_2, \ldots, a_{k-1}])$</span>.</p>
  <p>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.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-27T18:30:34.197Z
Answers.Text: 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.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-27T18:42:56.020Z
Answers.Text: Yeah, that's why I mentioned combinatorial optimization in the last line of my answer.
Answers.UserDisplayName: Robby Goetschalckx
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-27T14:59:50.013Z
Answers.LastActivityDate: 2020-08-27T14:59:50.013Z
Answers.UserDisplayName: Robby Goetschalckx
Body: <p>I have a scheduling problem in which there are <span class="math-container">$n$</span> slots and <span class="math-container">$m$</span> clients. I am trying to solve the problem using Q-learning so I have made the following state-action model.</p>
  <p>A state <span class="math-container">$s_t$</span> is given by the current slot <span class="math-container">$t=1,2,\ldots,n$</span> and an action <span class="math-container">$a_t$</span> at slot <span class="math-container">$t$</span> is given by one client, <span class="math-container">$a_t\in\{1,2,\ldots,m\}$</span>. In my situation, I do not have any reward associated with a state-action pair <span class="math-container">$(s_t,a_t)$</span> until the terminal state which is the last slot. In other words, for all <span class="math-container">$s_t\in\{1,2,\ldots,n-1\}$</span>, the reward is <span class="math-container">$0$</span> and for <span class="math-container">$s_t=n$</span> I can compute the reward given <span class="math-container">$(a_1,a_2,\ldots,a_n)$</span>.</p>
  <p>In this situation, the Q table, <span class="math-container">$Q(s_t,a_t)$</span>, will contain only zeros except for the last row in which it will contain the updated reward.</p>
  <p>Can I still apply Q-learning in this situation? Why do I need a Q table if I only use the last row?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-24T03:38:09.203Z
Comments.Text: Your question is very similar to [this one](https://ai.stackexchange.com/q/12189/2444). Given that you provide an example of a specific problem, I will not close it as an exact duplicate.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><q-learning><reward-functions><sparse-rewards><combinatorial-optimization>
Title: How to apply Q-learning when rewards is only available at the last state?
UserDisplayName: zdm
ThreadText: # How to apply Q-learning when rewards is only available at the last state?
  
  (Asked by: username_0 on 2020-08-27)
  
  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?
  
  **Tags:** reinforcement-learning, q-learning, reward-functions, sparse-rewards, combinatorial-optimization
  
  > **Comments:**
  > **username_1**: Your question is very similar to [this one](https://ai.stackexchange.com/q/12189/2444). Given that you provide an example of a specific problem, I will not close it as an exact duplicate.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2020-08-27. Score: 3 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_4**: 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.  
  > **username_3**: Yeah, that's why I mentioned combinatorial optimization in the last line of my answer.  
  
  ---
  
  ### Answer by username_2 on 2020-08-27. Score: 1
  
  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.
  
  
  ---
  
  