Answers.Body: <p>I found out a concept called 'Experience Replay', which trains a single step every time a new data sample is added instead of training to max epochs.</p>
  <p>That is, instead of this training loop:</p>
  <pre><code>for i in range(max_paces):
      find action for max reward;
      add to trajectory to make inp;
      train(batch_size=len(inp), epochs=max_epochs)
  </code></pre>
  <p>Do training this way (for a single-episode ML problem, no incremental):</p>
  <pre><code>for i in range(max_epochs):
      reset environment;
  
      for j in range(max_paces):
          find action for max reward;
          add to trajectory to make inp;
          train(batch_size=len(inp), epochs=1)
  </code></pre>
  <p>Do training this way (for a multi-episode ML problem, incremental data):</p>
  <pre><code>for i in range(max_epochs):
      reset environment;
      inc_trajectory = get_random_past_data();
  
      for j in range(max_paces):
          find action for max reward;
          add to inc_trajectory to make inp;
          train(batch_size=len(inp), epochs=1)
  </code></pre>
  <p>For multiple-episode problems especially those problems with unlimited episodes, the training loop needs to <strong>forget</strong> (ie. exclude from training) old episodes which are very distant in the past, or <strong>select a random number</strong> of old episodes (consider them <strong>a batch</strong>, random batch) to be in every round of experience replay. Anyway, without eliminating some old data, the amount of training data are too much since it's unlimited number of episodes.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-22T05:11:25.753Z
Answers.LastActivityDate: 2021-01-28T02:48:14.553Z
Answers.LastEditDate: 2021-01-28T02:48:14.553Z
Answers.UserDisplayName: Dan D.
Body: <p>I have a problem similar to the vehicle routing problem (VRP) that I want to solve with reinforcement learning. In this problem, the agent starts from the point <span class="math-container">$(x_0, y_0)$</span>, then it needs to travel through <span class="math-container">$N$</span> other points, <span class="math-container">$(x_1, y_1), \dots, (x_n, y_n)$</span>. The goal is to minimize the distance traveled.</p>
  <p>Right now, I am modeling a state as a point <span class="math-container">$(x, y)$</span>. There are 8 possible actions: go east, go north-east, go north, go north-west, go-west, go south-west, go south, go south-east. Each action goes by a pace of 100 metres.</p>
  <p>After reaching near a destination point, that destination point is removed from the list of destination points.</p>
  <p>The reward is the reciprocal of total distance until all destination points reached (there's a short optimisation to arrange the remaining points for a better reward).</p>
  <p>I'm using a DNN model to keep the policy of a reinforcement learning agent, so this DNN maps a certain state to suitable action.</p>
  <p>However, after every action of the agent with a good reward, the training data are added with 1 more sample, it's kinda incremental learning.</p>
  <p><strong>Should the policy model be trained again and again with every new sample added in</strong>? This does take too much time.</p>
  <p>Any better RL approach to the problem above?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T02:48:43.017Z
Comments.Text: Hello. Which RL algorithm are you using or planning to use to find the policy?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T02:50:07.687Z
Comments.Text: i may brute force, or i may do some greedy to find good rewards
Comments.UserDisplayName: Dan D.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T02:51:25.047Z
Comments.Text: Why don't you want to use some existing RL algorithm, such as Q-learning? Can you please describe more in detail your problem that you're trying to solve with RL (i.e. state space, action space and reward function)? Is this a toy problem that you came up with?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T03:03:23.723Z
Comments.Text: @nbro i've just added some details in the question
Comments.UserDisplayName: Dan D.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T03:08:04.633Z
Comments.Text: Thanks! Your post is way clearer now :) btw, you can use [mathjax/latex on this site](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference). As far as I recall, one good approach to the travelling salesman problem (something similar to what you're trying to do) are **ant colony optimization** algorithms. I don't know if RL is the best approach for this problem, but it can certainly be applied to this problem too.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T03:10:40.503Z
Comments.Text: @nbro i know RL isn't good for TSP, just trying out to see whether it's better than the supervised model
Comments.UserDisplayName: Dan D.
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T03:11:41.457Z
Comments.Text: Ok, then I think you should clarify that you want to use RL (and _not_ another approach), otherwise, people may think that you're also looking for other types of solutions given your question "Any better tactics for the problem above? ". Btw, ACO algorithms are not necessarily supervised. They are meta-heuristics, in the same way that genetic algorithms are also meta-heuristics.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-21T15:27:12.767Z
Comments.Text: do you have to use the action space that you have proposed? I have seen TSP solved using RL but the action space is usually just the cities (here it would be your points), i.e. which city to visit next.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-01-22T02:05:16.063Z
Comments.Text: the model is DNN, and there r thousands of destinations, and won't be able to classify to destination indices (city indices)
Comments.UserDisplayName: Dan D.
Tags: <reinforcement-learning><training><deep-rl><incremental-learning><travelling-salesman-problem>
Title: How to train a policy model incrementally to solve a problem similar to the vehicle routing problem?
UserDisplayName: Dan D.
ThreadText: # How to train a policy model incrementally to solve a problem similar to the vehicle routing problem?
  
  (Asked by: username_0 on 2021-01-21)
  
  I have a problem similar to the vehicle routing problem (VRP) that I want to solve with reinforcement learning. In this problem, the agent starts from the point $(x\_0, y\_0)$, then it needs to travel through $N$ other points, $(x\_1, y\_1), \dots, (x\_n, y\_n)$. The goal is to minimize the distance traveled.
  
  Right now, I am modeling a state as a point $(x, y)$. There are 8 possible actions: go east, go north-east, go north, go north-west, go-west, go south-west, go south, go south-east. Each action goes by a pace of 100 metres.
  
  After reaching near a destination point, that destination point is removed from the list of destination points.
  
  The reward is the reciprocal of total distance until all destination points reached (there's a short optimisation to arrange the remaining points for a better reward).
  
  I'm using a DNN model to keep the policy of a reinforcement learning agent, so this DNN maps a certain state to suitable action.
  
  However, after every action of the agent with a good reward, the training data are added with 1 more sample, it's kinda incremental learning.
  
  **Should the policy model be trained again and again with every new sample added in**? This does take too much time.
  
  Any better RL approach to the problem above?
  
  **Tags:** reinforcement-learning, training, deep-rl, incremental-learning, travelling-salesman-problem
  
  > **Comments:**
  > **username_1**: Hello. Which RL algorithm are you using or planning to use to find the policy?  
  > **username_0**: i may brute force, or i may do some greedy to find good rewards  
  > **username_1**: Why don't you want to use some existing RL algorithm, such as Q-learning? Can you please describe more in detail your problem that you're trying to solve with RL (i.e. state space, action space and reward function)? Is this a toy problem that you came up with?  
  > **username_0**: @username_1 i've just added some details in the question  
  > **username_1**: Thanks! Your post is way clearer now :) btw, you can use [mathjax/latex on this site](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference). As far as I recall, one good approach to the travelling salesman problem (something similar to what you're trying to do) are **ant colony optimization** algorithms. I don't know if RL is the best approach for this problem, but it can certainly be applied to this problem too.  
  > **username_0**: @username_1 i know RL isn't good for TSP, just trying out to see whether it's better than the supervised model  
  > **username_1**: Ok, then I think you should clarify that you want to use RL (and _not_ another approach), otherwise, people may think that you're also looking for other types of solutions given your question "Any better tactics for the problem above? ". Btw, ACO algorithms are not necessarily supervised. They are meta-heuristics, in the same way that genetic algorithms are also meta-heuristics.  
  > **username_2**: do you have to use the action space that you have proposed? I have seen TSP solved using RL but the action space is usually just the cities (here it would be your points), i.e. which city to visit next.  
  > **username_0**: the model is DNN, and there r thousands of destinations, and won't be able to classify to destination indices (city indices)  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-01-22. Score: 0 | Accepted answer
  
  I found out a concept called 'Experience Replay', which trains a single step every time a new data sample is added instead of training to max epochs.
  
  That is, instead of this training loop:
  
  ```
  for i in range(max_paces):
      find action for max reward;
      add to trajectory to make inp;
      train(batch_size=len(inp), epochs=max_epochs)
  
  ```
  
  Do training this way (for a single-episode ML problem, no incremental):
  
  ```
  for i in range(max_epochs):
      reset environment;
  
      for j in range(max_paces):
          find action for max reward;
          add to trajectory to make inp;
          train(batch_size=len(inp), epochs=1)
  
  ```
  
  Do training this way (for a multi-episode ML problem, incremental data):
  
  ```
  for i in range(max_epochs):
      reset environment;
      inc_trajectory = get_random_past_data();
  
      for j in range(max_paces):
          find action for max reward;
          add to inc_trajectory to make inp;
          train(batch_size=len(inp), epochs=1)
  
  ```
  
  For multiple-episode problems especially those problems with unlimited episodes, the training loop needs to **forget** (ie. exclude from training) old episodes which are very distant in the past, or **select a random number** of old episodes (consider them **a batch**, random batch) to be in every round of experience replay. Anyway, without eliminating some old data, the amount of training data are too much since it's unlimited number of episodes.
  
  
  ---
  
  