Answers.Body: <p>In short it looks like you have constructed a valid reinforcement learning method, but it does not have much in common with Monte Carlo Tree Search. It may have some weaknesses compared to more established methods, that means it will work better in some environments rather than others.</p>
  <p>Your approach may be novel, in that you have combined ideas into a method which has not been used in this exact form before. However, it is following the principles of general policy improvement (GPI):</p>
  <ul>
  <li><p>Estimate action values of a current policy.</p>
  </li>
  <li><p>Create a new policy by maximising action choices with respect to latest estimates.</p>
  </li>
  <li><p>Set current policy to new policy and repeat.</p>
  </li>
  </ul>
  <p>Your method covers exploration with a deterministic policy by sweeping through a list of state and action pairs. This resembles policy iteration, or perhaps exploring starts in Monte Carlo control. It evaluates each state/action pair by following the current policy up to a time step horizon. This has some weakness, but it may work well enough in some cases.</p>
  <p>The depth iteration is more complex to analyse. It is not doing what you suggest - i.e. it does not make the whole algorithm equivalent somehow to a tree search. Technically the value estimates with a short horizon will be poor, biased estimates of true value in the general case, but on the plus side they may still help differentiate between good and bad action choices in some situations. It may even help as a form of curriculum learning by gathering and training on data about immediately obvious decisions first (again I expect that would be situational, not something you could rely on).</p>
  <p>Overall, although you seem to have found a nice solution for your racing game, I think your method will work unreliably in a general case. Environments with stochastic state transitions and rewards would be a major problem, and this is not something you could fix without major changes to the algorithm.</p>
  <p>I could suggest that you to try one or more standard published methods, such as DQN, A3C etc, and compare them with your approach on the same environments in different ways. E.g. how much time and computation it takes to train to an acceptable level, or how close to optimal each method can get to.</p>
  <p>The main comparison with Monte Carlo Tree Search is that you evaluate each state, action pair with a kind of rollout. There is lots more going on in MCTS that you are not doing though, and the iteration with longer rollouts each time is not like anything in MCTS and does not compensate for missing parts of MCTS in your algorithm.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-18T07:47:06.813Z
Answers.Text: Wow, that's a lot to digest. Indeed, my environment is deterministic, so I'm not worried about randomness. Could you elaborate on what the weaknesses are (would they only apply to stochastic environments)? Also: agent.depth=0 is trivially tree search...agent.depth=1 is tree search (but using the NN to estimate the second branch)...it's agent.depth=2 and beyond where I'm not clear on what's happening. I am working on implementing the others you mentioned..
Answers.UserDisplayName: Kricket
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-18T10:01:18.247Z
Answers.Text: @Kricket: The main weakness is low depth causing the valuations you are using to not be accurate. So as well as problems with stochastic environments, those with sparse rewards could be an issue. Other GPI approaches track value functions longer-term or run to end of episodes when sampling. Your method runs truncated evaluations then throws away all the data after each policy update.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T21:48:33.693Z
Answers.LastActivityDate: 2021-03-17T21:57:49.583Z
Answers.LastEditDate: 2021-03-17T21:57:49.583Z
Answers.UserDisplayName: Neil Slater
Body: <p>I'm using a Neural Network as an agent in a simple car racing game. My goal is to train the network to imitate a brute-force tree search to an arbitrary depth.</p>
  <p>My algorithm goes something like the following:</p>
  <ul>
  <li>The agent starts with depth 0</li>
  <li>Generate a bunch of test states</li>
  <li>For each test state <code>s</code>:
  <ul>
  <li>For each action <code>a</code>:
  <ul>
  <li><code>s' = env.step(s, a)</code></li>
  <li><code>for x in range(agent.depth): s' = env.step(s', agent.predict(s'))</code></li>
  <li>calculate reward at state <code>s'</code></li>
  </ul>
  </li>
  <li>Set the label for test state <code>s</code> as whichever action <code>a</code> produced the highest reward</li>
  </ul>
  </li>
  <li>Train the agent using the test states and labels, and increment <code>agent.depth</code></li>
  <li>Loop until desired depth</li>
  </ul>
  <p>The idea is that an agent trained in this way to depth N should produce output close to a brute-force tree search to depth N...so by using it to play out N moves, it should be able to find me the best final state at that depth. In practice, I've found that it performs somewhere between N and N-1 (but of course it never reaches 100% accuracy).</p>
  <p>My question is: what is the name of this algorithm? When I search for tree search with playout, everything talks about MCTS. But since there's no randomness here (the first step is to try ALL actions), what would this be called instead?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T09:30:27.597Z
Comments.Text: How are you picking your set of test states?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T10:15:05.733Z
Comments.Text: I iterate through the range of possible states (at regular intervals). Sometimes I augment this dataset by taking each one and playing through it a few random moves (saving each state as it goes).
Comments.UserDisplayName: Kricket
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T10:40:01.103Z
Comments.Text: I am not sure I understand. What is the "range of possible states", and do you really mean "iterate" as in you use *all* of them in sequence? If so, what does augmentation give you (because you already have all states in the dataset)? Did you perhaps mean that you *sample* a set number from all possible states, or is perhaps the iteration somehow spread out so that only part of it is completed for each generation step?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T10:50:42.000Z
Comments.Text: The state includes position, angle, and velocity. So, for example angle: `[i * 2 * math.pi / 10 for i in range(10)]`. By doing this for position and velocity as well (within reasonable limits), I get a series of states spread throughout the state space. (Why is this relevant? My question is more about the approach to tree search, not how I come up with test data.)
Comments.UserDisplayName: Kricket
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T11:25:46.013Z
Comments.Text: It is relevant because I think that you are not really doing tree search at all. Your approach is *only* working because of the state sampling. I want to ascertain what that is in order to be sure. So, to be clear the state space is continuous, and you are sampling points from it in a grid pattern?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T12:04:23.487Z
Comments.Text: Yes, continuous state space, sampled in a grid pattern. I kinda get that it's not "really" tree search (or rather, it's tree search to depth 1, followed by a NN-guided playout), but then why does it produce results similar to a real tree search? For example, if I do 3 iterations of training, its performance is somewhere between tree search of depth 2 and 3. If I go to 4 iterations, the performance is between tree search of depth 3 and 4. (The deeper I go, however, the less accurate it gets...but I would assume that's due to the network architecture/hyperparameters...)
Comments.UserDisplayName: Kricket
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T12:08:51.290Z
Comments.Text: I should note that actually, I get better results if I skew my grid pattern to have finer granularity near the points near the turns in the race course. My guess is that, when far from a turn, the correct answer is simple - just head for the turn. When closer, finer control is needed to turn/accelerate at just the right time to maximize future rewards.
Comments.UserDisplayName: Kricket
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-17T12:08:52.623Z
Comments.Text: Thanks for the clarifications. I'll explain why I think it works and what the limitations are likely to be in an answer soon-ish.
Comments.UserDisplayName: Neil Slater
Tags: <neural-networks><monte-carlo-tree-search><tree-search>
Title: What is this algorithm? Is it a variant of Monte-Carlo Tree Search?
UserDisplayName: Kricket
ThreadText: # What is this algorithm? Is it a variant of Monte-Carlo Tree Search?
  
  (Asked by: username_0 on 2021-03-17)
  
  I'm using a Neural Network as an agent in a simple car racing game. My goal is to train the network to imitate a brute-force tree search to an arbitrary depth.
  
  My algorithm goes something like the following:
  
  * The agent starts with depth 0
  * Generate a bunch of test states
  * For each test state `s`:
    + For each action `a`:
      - `s' = env.step(s, a)`
      - `for x in range(agent.depth): s' = env.step(s', agent.predict(s'))`
      - calculate reward at state `s'`
    + Set the label for test state `s` as whichever action `a` produced the highest reward
  * Train the agent using the test states and labels, and increment `agent.depth`
  * Loop until desired depth
  
  The idea is that an agent trained in this way to depth N should produce output close to a brute-force tree search to depth N...so by using it to play out N moves, it should be able to find me the best final state at that depth. In practice, I've found that it performs somewhere between N and N-1 (but of course it never reaches 100% accuracy).
  
  My question is: what is the name of this algorithm? When I search for tree search with playout, everything talks about MCTS. But since there's no randomness here (the first step is to try ALL actions), what would this be called instead?
  
  **Tags:** neural-networks, monte-carlo-tree-search, tree-search
  
  > **Comments:**
  > **username_1**: How are you picking your set of test states?  
  > **username_0**: I iterate through the range of possible states (at regular intervals). Sometimes I augment this dataset by taking each one and playing through it a few random moves (saving each state as it goes).  
  > **username_1**: I am not sure I understand. What is the "range of possible states", and do you really mean "iterate" as in you use *all* of them in sequence? If so, what does augmentation give you (because you already have all states in the dataset)? Did you perhaps mean that you *sample* a set number from all possible states, or is perhaps the iteration somehow spread out so that only part of it is completed for each generation step?  
  > **username_0**: The state includes position, angle, and velocity. So, for example angle: `[i * 2 * math.pi / 10 for i in range(10)]`. By doing this for position and velocity as well (within reasonable limits), I get a series of states spread throughout the state space. (Why is this relevant? My question is more about the approach to tree search, not how I come up with test data.)  
  > **username_1**: It is relevant because I think that you are not really doing tree search at all. Your approach is *only* working because of the state sampling. I want to ascertain what that is in order to be sure. So, to be clear the state space is continuous, and you are sampling points from it in a grid pattern?  
  > **username_0**: Yes, continuous state space, sampled in a grid pattern. I kinda get that it's not "really" tree search (or rather, it's tree search to depth 1, followed by a NN-guided playout), but then why does it produce results similar to a real tree search? For example, if I do 3 iterations of training, its performance is somewhere between tree search of depth 2 and 3. If I go to 4 iterations, the performance is between tree search of depth 3 and 4. (The deeper I go, however, the less accurate it gets...but I would assume that's due to the network architecture/hyperparameters...)  
  > **username_0**: I should note that actually, I get better results if I skew my grid pattern to have finer granularity near the points near the turns in the race course. My guess is that, when far from a turn, the correct answer is simple - just head for the turn. When closer, finer control is needed to turn/accelerate at just the right time to maximize future rewards.  
  > **username_1**: Thanks for the clarifications. I'll explain why I think it works and what the limitations are likely to be in an answer soon-ish.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-03-17. Score: 2 | Accepted answer
  
  In short it looks like you have constructed a valid reinforcement learning method, but it does not have much in common with Monte Carlo Tree Search. It may have some weaknesses compared to more established methods, that means it will work better in some environments rather than others.
  
  Your approach may be novel, in that you have combined ideas into a method which has not been used in this exact form before. However, it is following the principles of general policy improvement (GPI):
  
  * Estimate action values of a current policy.
  * Create a new policy by maximising action choices with respect to latest estimates.
  * Set current policy to new policy and repeat.
  
  Your method covers exploration with a deterministic policy by sweeping through a list of state and action pairs. This resembles policy iteration, or perhaps exploring starts in Monte Carlo control. It evaluates each state/action pair by following the current policy up to a time step horizon. This has some weakness, but it may work well enough in some cases.
  
  The depth iteration is more complex to analyse. It is not doing what you suggest - i.e. it does not make the whole algorithm equivalent somehow to a tree search. Technically the value estimates with a short horizon will be poor, biased estimates of true value in the general case, but on the plus side they may still help differentiate between good and bad action choices in some situations. It may even help as a form of curriculum learning by gathering and training on data about immediately obvious decisions first (again I expect that would be situational, not something you could rely on).
  
  Overall, although you seem to have found a nice solution for your racing game, I think your method will work unreliably in a general case. Environments with stochastic state transitions and rewards would be a major problem, and this is not something you could fix without major changes to the algorithm.
  
  I could suggest that you to try one or more standard published methods, such as DQN, A3C etc, and compare them with your approach on the same environments in different ways. E.g. how much time and computation it takes to train to an acceptable level, or how close to optimal each method can get to.
  
  The main comparison with Monte Carlo Tree Search is that you evaluate each state, action pair with a kind of rollout. There is lots more going on in MCTS that you are not doing though, and the iteration with longer rollouts each time is not like anything in MCTS and does not compensate for missing parts of MCTS in your algorithm.
  
  > **Comments:**
  > **username_0**: Wow, that's a lot to digest. Indeed, my environment is deterministic, so I'm not worried about randomness. Could you elaborate on what the weaknesses are (would they only apply to stochastic environments)? Also: agent.depth=0 is trivially tree search...agent.depth=1 is tree search (but using the NN to estimate the second branch)...it's agent.depth=2 and beyond where I'm not clear on what's happening. I am working on implementing the others you mentioned..  
  > **username_1**: @username_0: The main weakness is low depth causing the valuations you are using to not be accurate. So as well as problems with stochastic environments, those with sparse rewards could be an issue. Other GPI approaches track value functions longer-term or run to end of episodes when sampling. Your method runs truncated evaluations then throws away all the data after each policy update.  
  
  ---
  
  