Body: <p>I try to implement RL to a case something like this:</p>
  
  <blockquote>
    <p>This game consist of several rounds. Every round the players need to generate a maze that consists of rooms. There are around 1000 different available rooms with different properties. At the beginning of a round, each player will be given 10 rooms one-by-one (the sequence is same for each player) from 1000 that available, then he/she try to create a maze from the taken rooms (by arranging each room). After the maze is done there is a Game Master who will judge the maze (give a score between 0-100). The player never know how the Game Master judges the maze, it can be judged based on the level of difficulty that is produced, the order of the room we compose, or others. The player who got the best score for the given rooms will win this round.</p>
    
    <p>in this case, I have around 100,000 "perfect" mazes that have been created from different room combination and got a perfect score. I use this maze as episodes and try to train RL-Agent to find the pattern of how the Game Master judges a maze. For your information, there are rooms that not exist in the 100,000 perfect mazes, but I hope the RL-Agent can use its properties to find similar rooms that exist in  the "perfect" mazes, and make it as a reference</p>
  </blockquote>
  
  <p>This case is different from other RL environments that I've ever met before, generating an episode is not an easy task because it needs an expert to validate it (The Game Master). So you could say, I can only build the RL agent using that 100,000 episodes.</p>
  
  <p>But, even though it only consists of 100,000 episodes, my case has millions of states, so I plan to use Q-Learning with Neural Net as approximator.</p>
  
  <p>My question is:</p>
  
  <ul>
  <li>in this case, am I still need the Experience Replay process (I am afraid I don't need it because of the small number of available episodes)? </li>
  <li>has this case ever happened before? What is the best approach to deal with cases where the number of episodes is limited?</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-26T11:04:39.760Z
Comments.Text: Is your goal to find a good policy for the environment? How will you test your new policy?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-27T08:23:02.230Z
Comments.Text: @Neil Slater I'll test the new policy by test it to the available episodes that unused before (like "train-test" split concept). But it's just for the evaluation in the final phase
Comments.UserDisplayName: malioboro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-27T09:31:02.890Z
Comments.Text: That may not work very well, depending on what data you hold. But not important to this question - perhaps you can ask another about that. I was asking to try and get a sense for how you might use the data. I have a better clarifying question now:
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-27T09:33:44.830Z
Comments.Text: What kind of behaviour do your 100,000 pre-defined episodes represent? Is it mainly an "expert policy" which attempts to be optimal, or is it more varied than that? Could you give a little bit of detail on how the 100,000 "sequences" were generated? Please [edit] into the question. That could help guide an answer. An important detail would be if the sequences were generated using a known policy for instance (because then you could use importance sampling)
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T06:24:38.650Z
Comments.Text: @Neil Slater I've updated my question
Comments.UserDisplayName: malioboro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T07:17:39.410Z
Comments.Text: Thanks. I *think* here that your problem is not just "limited number of episodes" but also that you only have historical data, you cannot easily run the algorithm online to test or improve any new policy.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T07:56:46.467Z
Comments.Text: Can you also clarify: Do you have scores for any non-perfect mazes? One of your goals is to predict the score, in order to *find* perfect scores. Having only perfect examples and no examples of other, lower scores, is going to severely limit your ability to predict the end score. To most ML, it will look like everything always gets a perfect score (e.g. this is similar to writing an algorithm to recognise cats and feeding it only cat pictures during training - it will never get to know what things are not cats).
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T09:44:04.767Z
Comments.Text: That's true, for now, as the maze is just a permutation of given rooms, I use a method to compute a score of a non-perfect maze by comparing a maze to another maze that consists of the same rooms (something like edit distance).
Comments.UserDisplayName: malioboro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T09:45:38.597Z
Comments.Text: @mailoboro: that's a different model, sort of an "expert system" that you have built. Training on that is possible, but your agent will optimise to what your model thinks, not any real values. Do you have actual scores from the Game Master for non-perfect mazes? Alternatively, if your model is good enough to stand in for the Game Master, then you no longer have limited data to work with
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T09:53:30.600Z
Comments.Text: No, I don't have the score for non-perfect mazes. Actually, my purpose is to create an RL to guess how the game master works so it's like to mimic an expert in expert system. I believe this is a "hard" task especially with limited resources, but I hope I can create at least "good enough" expert using RL
Comments.UserDisplayName: malioboro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-03T09:57:40.170Z
Comments.Text: To know how the game master works, if you only sample "perfect" results and don't understand how to get other scores, then you have a hard problem regardless of using RL or not. You can still try to copy the "perfect" items, but will have very little idea of how well that is going with no examples from non-perfect items
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><q-learning><experience-replay>
Title: Reinforcement Learning with limited number of episodes
UserDisplayName: malioboro
ThreadText: # Reinforcement Learning with limited number of episodes
  
  (Asked by: username_0 on 2019-03-26)
  
  I try to implement RL to a case something like this:
  
  > This game consist of several rounds. Every round the players need to generate a maze that consists of rooms. There are around 1000 different available rooms with different properties. At the beginning of a round, each player will be given 10 rooms one-by-one (the sequence is same for each player) from 1000 that available, then he/she try to create a maze from the taken rooms (by arranging each room). After the maze is done there is a Game Master who will judge the maze (give a score between 0-100). The player never know how the Game Master judges the maze, it can be judged based on the level of difficulty that is produced, the order of the room we compose, or others. The player who got the best score for the given rooms will win this round.
  >
  > in this case, I have around 100,000 "perfect" mazes that have been created from different room combination and got a perfect score. I use this maze as episodes and try to train RL-Agent to find the pattern of how the Game Master judges a maze. For your information, there are rooms that not exist in the 100,000 perfect mazes, but I hope the RL-Agent can use its properties to find similar rooms that exist in the "perfect" mazes, and make it as a reference
  
  This case is different from other RL environments that I've ever met before, generating an episode is not an easy task because it needs an expert to validate it (The Game Master). So you could say, I can only build the RL agent using that 100,000 episodes.
  
  But, even though it only consists of 100,000 episodes, my case has millions of states, so I plan to use Q-Learning with Neural Net as approximator.
  
  My question is:
  
  * in this case, am I still need the Experience Replay process (I am afraid I don't need it because of the small number of available episodes)?
  * has this case ever happened before? What is the best approach to deal with cases where the number of episodes is limited?
  
  **Tags:** reinforcement-learning, q-learning, experience-replay
  > **Comments:**
  > **username_1**: Is your goal to find a good policy for the environment? How will you test your new policy?  
  > **username_0**: @Neil Slater I'll test the new policy by test it to the available episodes that unused before (like "train-test" split concept). But it's just for the evaluation in the final phase  
  > **username_1**: That may not work very well, depending on what data you hold. But not important to this question - perhaps you can ask another about that. I was asking to try and get a sense for how you might use the data. I have a better clarifying question now:  
  > **username_1**: What kind of behaviour do your 100,000 pre-defined episodes represent? Is it mainly an "expert policy" which attempts to be optimal, or is it more varied than that? Could you give a little bit of detail on how the 100,000 "sequences" were generated? Please [edit] into the question. That could help guide an answer. An important detail would be if the sequences were generated using a known policy for instance (because then you could use importance sampling)  
  > **username_0**: @Neil Slater I've updated my question  
  > **username_1**: Thanks. I *think* here that your problem is not just "limited number of episodes" but also that you only have historical data, you cannot easily run the algorithm online to test or improve any new policy.  
  > **username_1**: Can you also clarify: Do you have scores for any non-perfect mazes? One of your goals is to predict the score, in order to *find* perfect scores. Having only perfect examples and no examples of other, lower scores, is going to severely limit your ability to predict the end score. To most ML, it will look like everything always gets a perfect score (e.g. this is similar to writing an algorithm to recognise cats and feeding it only cat pictures during training - it will never get to know what things are not cats).  
  > **username_0**: That's true, for now, as the maze is just a permutation of given rooms, I use a method to compute a score of a non-perfect maze by comparing a maze to another maze that consists of the same rooms (something like edit distance).  
  > **username_1**: @mailoboro: that's a different model, sort of an "expert system" that you have built. Training on that is possible, but your agent will optimise to what your model thinks, not any real values. Do you have actual scores from the Game Master for non-perfect mazes? Alternatively, if your model is good enough to stand in for the Game Master, then you no longer have limited data to work with  
  > **username_0**: No, I don't have the score for non-perfect mazes. Actually, my purpose is to create an RL to guess how the game master works so it's like to mimic an expert in expert system. I believe this is a "hard" task especially with limited resources, but I hope I can create at least "good enough" expert using RL  
  > **username_1**: To know how the game master works, if you only sample "perfect" results and don't understand how to get other scores, then you have a hard problem regardless of using RL or not. You can still try to copy the "perfect" items, but will have very little idea of how well that is going with no examples from non-perfect items  
  
  ---
  
  ## 0 answers
  
  