Body: <p>How can I guide my RL agent to solve tasks in the correct order?</p>
  <p>I'm trying to train an agent using reinforcement learning, similar to MuZero. The goal is to solve 4 tasks, A/B/C/D. Each task involves two actions, X1/X2. Initially, only action A1 is possible. Performing it enables A2 and B1; B1 enables B1 and C1; C1 enables C2 and D1; D1 enables D2. There are also some other actions that aren't listed here - they all prevent the successful termination of at least one of the tasks.
  Crucially, performing any action X2 before D1 is done will permanently disable D1. So the only winning policy is A1&gt;B1&gt;C1&gt;D1&gt;{A2, B2, C2, D2 in any order}</p>
  <p>To guide the training, I've defined small rewards for solving each task, and a large one for solving all four. I've set the discounting factor to 1.0, so there should be no downside to not immediately doing some X2 step.</p>
  <p>Unfortunately, the agent never learns to do all A1-D1 steps first. It manages to do A1 and B1 first, sometimes even C1, but never all 4. It then completes some task A-C and thus fails to solve task D.</p>
  <p>I noticed that my policy network learns to assign a prior probability of ~1 to A1&gt;A2, strongly biasing the MCTS to explore this path. I assume the reason is that by random exploration the agent will often do A1&gt;A2&gt;... and get a reward. But A1&gt;B1&gt;C1&gt;D1&gt;A2 is way less likely. So the network is well-trained in predicting the reward for A1&gt;A2, but less well-trained for the longer game sequences. If it cannot predict the reward there, the MCTS is biased to do A1&gt;A2. This causes the policy network to also learn that this action should have a high prior probability, further biasing the MCTS, creating a feedback loop.</p>
  <p>How can this be prevented? Would it be enough to increase the temperature? If so, should I only increase the temperature for sampling from the distribution computed by the MCTS, or should I also increase the <span class="math-container">$c_1$</span> in the UCB formula? That should increase the exploring within MCTS, and reduce the focus on the rewards.</p>
  <p>I guess I could also remove the intermediate rewards, but then my signal will be extremely sparse.</p>
  <p><a href="https://i.sstatic.net/fQlNT.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fQlNT.png" alt="UCB formula" /></a></p>
  <p>I know that I could enforce the order of tasks using the environment, but I want the make the agent learn this by itself.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-24T06:49:37.347Z
Comments.Text: This seems like a simple toy task. You say that "There are also some other actions that aren't listed here" - what is the ratio of number of possible actions to the 8 you describe in more detail?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-24T07:23:41.567Z
Comments.Text: Another important thing to clarify - what is your state representation?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-24T15:40:26.683Z
Comments.Text: @NeilSlater There are 26 actions. The given 8 actions are the "good" ones, all other 18 actions will prevent one of the tasks from succeeding. Not all actions are available in every state, I'm already masking them. But I made sure that the correct sequence of actions is possible
Comments.UserDisplayName: Christopher
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-24T15:49:02.897Z
Comments.Text: OK, cool. So what is the state representation that the agent uses to calculate the policy? i.e. the input into your policy method
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-10-24T17:35:02.983Z
Comments.Text: @NeilSlater It's a very simplified version of the AlpheDev setup: The state representation is a list of all previous actions (what values were moved from which memory locations to which other locations) and a snapshot of the current memory. The representation network has a transformer architecture to process the sequence of instructions, the resulting representation is combined with a MLP-processed embedding of the memory values
Comments.UserDisplayName: Christopher
Tags: <reinforcement-learning><monte-carlo-tree-search><upper-confidence-bound><muzero>
Title: RL agent focusses too much on early rewards, even with no discounting
UserDisplayName: Christopher
ThreadText: # RL agent focusses too much on early rewards, even with no discounting
  
  (Asked by: username_0 on 2023-10-23)
  
  How can I guide my RL agent to solve tasks in the correct order?
  
  I'm trying to train an agent using reinforcement learning, similar to MuZero. The goal is to solve 4 tasks, A/B/C/D. Each task involves two actions, X1/X2. Initially, only action A1 is possible. Performing it enables A2 and B1; B1 enables B1 and C1; C1 enables C2 and D1; D1 enables D2. There are also some other actions that aren't listed here - they all prevent the successful termination of at least one of the tasks.
  Crucially, performing any action X2 before D1 is done will permanently disable D1. So the only winning policy is A1>B1>C1>D1>{A2, B2, C2, D2 in any order}
  
  To guide the training, I've defined small rewards for solving each task, and a large one for solving all four. I've set the discounting factor to 1.0, so there should be no downside to not immediately doing some X2 step.
  
  Unfortunately, the agent never learns to do all A1-D1 steps first. It manages to do A1 and B1 first, sometimes even C1, but never all 4. It then completes some task A-C and thus fails to solve task D.
  
  I noticed that my policy network learns to assign a prior probability of ~1 to A1>A2, strongly biasing the MCTS to explore this path. I assume the reason is that by random exploration the agent will often do A1>A2>... and get a reward. But A1>B1>C1>D1>A2 is way less likely. So the network is well-trained in predicting the reward for A1>A2, but less well-trained for the longer game sequences. If it cannot predict the reward there, the MCTS is biased to do A1>A2. This causes the policy network to also learn that this action should have a high prior probability, further biasing the MCTS, creating a feedback loop.
  
  How can this be prevented? Would it be enough to increase the temperature? If so, should I only increase the temperature for sampling from the distribution computed by the MCTS, or should I also increase the $c\_1$ in the UCB formula? That should increase the exploring within MCTS, and reduce the focus on the rewards.
  
  I guess I could also remove the intermediate rewards, but then my signal will be extremely sparse.
  
  [![UCB formula](https://i.sstatic.net/fQlNT.png)](https://i.sstatic.net/fQlNT.png)
  
  I know that I could enforce the order of tasks using the environment, but I want the make the agent learn this by itself.
  
  **Tags:** reinforcement-learning, monte-carlo-tree-search, upper-confidence-bound, muzero
  
  > **Comments:**
  > **username_1**: This seems like a simple toy task. You say that "There are also some other actions that aren't listed here" - what is the ratio of number of possible actions to the 8 you describe in more detail?  
  > **username_1**: Another important thing to clarify - what is your state representation?  
  > **username_0**: @username_1 There are 26 actions. The given 8 actions are the "good" ones, all other 18 actions will prevent one of the tasks from succeeding. Not all actions are available in every state, I'm already masking them. But I made sure that the correct sequence of actions is possible  
  > **username_1**: OK, cool. So what is the state representation that the agent uses to calculate the policy? i.e. the input into your policy method  
  > **username_0**: @username_1 It's a very simplified version of the AlpheDev setup: The state representation is a list of all previous actions (what values were moved from which memory locations to which other locations) and a snapshot of the current memory. The representation network has a transformer architecture to process the sequence of instructions, the resulting representation is combined with a MLP-processed embedding of the memory values  
  
  ---
  
  ## 0 answers
  
  