Answers.Body: <p>Your concern touches upon a fundamental challenge in MCTS when applied to games or decision trees with continuous or non-binary payoffs. In such cases distinguishing between actions that have similar but slightly different expected values can be challenging for MCTS as you've rightly shown. Intuitively due to the small difference between the payoffs of actions 1b and action 2 of your example, a significant number of rollouts are needed to reduce the variance uncertainty in one of the estimated UCB values of these actions.</p>
  <p>Besides using cutoff values from domain knowledge, in general decreasing the exploration parameter of UCB may reduce unnecessary exploration when the differences in payoffs are small, leading to faster convergence. Similarly due to the large variance of some action value in your example, in general you can add a variance term with its coefficient parameter to the generic UCB formula. However, there's no general optimal values of these parameters and their careful tuning is also problem-dependent.</p>
  <p>If your domain knowledge indicates the importance of small value difference as you noted for the game of Go, then you can shape the reward function to amplify the differences between close scores. For example, using exponential transformation could make the difference between 0.8 and 0.9 more pronounced, encouraging faster convergence.</p>
  <p>Finally for decision trees or games with a large number of possible actions, progressive widening might help generally speaking. Instead of expanding all possible actions immediately, the algorithm focuses on the most promising ones first and incrementally expands actions as more simulations are performed.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-11T01:42:17.350Z
Answers.Text: UCB with variance looks promising to me.
Answers.UserDisplayName: user3785097
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-11T02:05:38.757Z
Answers.Text: Decreasing exploration: wouldn't visit count for  both 1a and 1b get reduced? Transforming score: exponentiation is like setting a high cutoff, it amplifies difference between 0.8 and 0.9, but makes 0.1 and 0.2 harder to distinguish. In fact, I think any nonlinear transform distorts risk preference.
Answers.UserDisplayName: user3785097
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-11T03:23:46.717Z
Answers.Text: @user3785097 As I've cautioned in my above answer that reward shaping definitely needs domain knowledge too as in your 0.1 vs 02 and 0.8 vs 0.9 cases in the game of Go, that's why there's hardly a universal computable score transforming formula for it to scale. Same goes exploration parameter C in the UCB formula as both action 1a/b and action 2 explorations would be decreased if C is decreased, and your own experiment can be viewed as fine tuning this parameter C to arrive at a stable convergent result for your specific case.
Answers.UserDisplayName: cinch
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-09-10T06:43:23.763Z
Answers.LastActivityDate: 2024-09-10T06:43:23.763Z
Answers.UserDisplayName: cinch
Body: <p>Consider this 1-player decision tree:</p>
  <p>Turn 1: action 1 or action 2. If action 2, payoff is 0.8 .</p>
  <p>Turn 2: if action 1 in turn 1, then choose between action 1a and 1b, with payoffs 0 and 0.9 respectively.</p>
  <pre><code>1 -- 1a (0) 
    \- 1b (0.9)
  2 (0.8)
  </code></pre>
  <p><a href="https://i.sstatic.net/Z4OXIvCm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Z4OXIvCm.png" alt="enter image description here" /></a></p>
  <p>Above is the calculation of UCB I did in spreadsheet(with exploration parameter=1.5). You see, it takes 90 roll-outs to find solution for a game tree that has only 3 leaves. This is only an example. I encountered this sort of behavior when implementing MCTS for larger game tree, so minimax is not a choice here.</p>
  <p>I know the problem is action 1b and action 2 have similar payoffs, if payoffs are only zero/one this wouldn't be an issue. But in many applications(Go, betting games, video game speed-run, real life decisions...) the goal is getting score rather than a simple win/loss. In those applications, the different between 0.8 and 0.9 would be huge(36 points in Go!).</p>
  <p>In AI for Go, this problem is solved by having a cutoff value for score, so we transform result score to zero/one. But this is kind of cheating, as we need to know the game value before hand to decide the correct cutoff.</p>
  <p>So what am I missing here? MCTS must be able to handle such a simple tree search, right?</p>
  
Tags: <monte-carlo-tree-search>
Title: MCTS can't handle tree search with range result values?
UserDisplayName: user3785097
ThreadText: # MCTS can't handle tree search with range result values?
  
  (Asked by: username_0 on 2024-09-10)
  
  Consider this 1-player decision tree:
  Turn 1: action 1 or action 2. If action 2, payoff is 0.8 .
  Turn 2: if action 1 in turn 1, then choose between action 1a and 1b, with payoffs 0 and 0.9 respectively.
  1 -- 1a (0) 
    \- 1b (0.9)
  2 (0.8)
  
  
  Above is the calculation of UCB I did in spreadsheet(with exploration parameter=1.5). You see, it takes 90 roll-outs to find solution for a game tree that has only 3 leaves. This is only an example. I encountered this sort of behavior when implementing MCTS for larger game tree, so minimax is not a choice here.
  I know the problem is action 1b and action 2 have similar payoffs, if payoffs are only zero/one this wouldn't be an issue. But in many applications(Go, betting games, video game speed-run, real life decisions...) the goal is getting score rather than a simple win/loss. In those applications, the different between 0.8 and 0.9 would be huge(36 points in Go!).
  In AI for Go, this problem is solved by having a cutoff value for score, so we transform result score to zero/one. But this is kind of cheating, as we need to know the game value before hand to decide the correct cutoff.
  So what am I missing here? MCTS must be able to handle such a simple tree search, right?
  
  **Tags:** monte-carlo-tree-search
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-09-10. Score: 0
  
  Your concern touches upon a fundamental challenge in MCTS when applied to games or decision trees with continuous or non-binary payoffs. In such cases distinguishing between actions that have similar but slightly different expected values can be challenging for MCTS as you've rightly shown. Intuitively due to the small difference between the payoffs of actions 1b and action 2 of your example, a significant number of rollouts are needed to reduce the variance uncertainty in one of the estimated UCB values of these actions.
  
  Besides using cutoff values from domain knowledge, in general decreasing the exploration parameter of UCB may reduce unnecessary exploration when the differences in payoffs are small, leading to faster convergence. Similarly due to the large variance of some action value in your example, in general you can add a variance term with its coefficient parameter to the generic UCB formula. However, there's no general optimal values of these parameters and their careful tuning is also problem-dependent.
  
  If your domain knowledge indicates the importance of small value difference as you noted for the game of Go, then you can shape the reward function to amplify the differences between close scores. For example, using exponential transformation could make the difference between 0.8 and 0.9 more pronounced, encouraging faster convergence.
  
  Finally for decision trees or games with a large number of possible actions, progressive widening might help generally speaking. Instead of expanding all possible actions immediately, the algorithm focuses on the most promising ones first and incrementally expands actions as more simulations are performed.
  
  > **Comments:**
  > **username_0**: UCB with variance looks promising to me.  
  > **username_0**: Decreasing exploration: wouldn't visit count for  both 1a and 1b get reduced? Transforming score: exponentiation is like setting a high cutoff, it amplifies difference between 0.8 and 0.9, but makes 0.1 and 0.2 harder to distinguish. In fact, I think any nonlinear transform distorts risk preference.  
  > **username_1**: @user3785097 As I've cautioned in my above answer that reward shaping definitely needs domain knowledge too as in your 0.1 vs 02 and 0.8 vs 0.9 cases in the game of Go, that's why there's hardly a universal computable score transforming formula for it to scale. Same goes exploration parameter C in the UCB formula as both action 1a/b and action 2 explorations would be decreased if C is decreased, and your own experiment can be viewed as fine tuning this parameter C to arrive at a stable convergent result for your specific case.  
  
  ---
  
  