Skip to main content
Share Your Experience: Take the 2024 Developer Survey
4 votes
Accepted

In MCTS, what to do if I do not want to simulate till the end of the game?

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ ...
Kostya's user avatar
  • 2,534
4 votes
Accepted

Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?

You can indeed use UCB in the RL setting. See e.g. section 38.5 Upper Confidence Bounds for Reinforcement Learning (page 521) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore for ...
nbro's user avatar
  • 40.8k
3 votes

Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?

Many techniques for the exploration/exploitation dilemma that are inspired by multi-armed bandit problems, such as UCB1, assume that you can explicitly enumerate all state-action pairs; in fact, multi-...
Dennis Soemers's user avatar
  • 10.3k
3 votes
Accepted

How do we reach at the formula for UCB action-selection in multi-armed bandit problem?

Here is an intuitive description/explanation. $c$ is there for a trade-off between exploration and exploitation. If $c=0$ then you only consider $Q_t(a)$ (no exploration). If $c \rightarrow \infty$ ...
Brale's user avatar
  • 2,406
3 votes

Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem?

The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature. Second thing to note would be that the performance of bandit algorithms is ...
user5093249's user avatar
2 votes

Should I use exploration strategy in Policy Gradient algorithms?

Neil Slater's answer is very nice, but I have a couple more suggestions: You can use entropy regularization. Basically, you modify your loss function to penalize low policy entropy (so less loss for ...
harwiltz's user avatar
  • 1,136
2 votes
Accepted

Should I use exploration strategy in Policy Gradient algorithms?

I believe that if I follow the policy (sample an action from the policy) I make use of exploration because each action has a certain probability so I will explore all actions for a given state. Yes, ...
Neil Slater's user avatar
  • 32.5k
2 votes

Why do we have two similar action selection strategies for UCB1?

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ ...
Namnamseo's user avatar
2 votes

Why do we use $X_{I_t,t}$ and $v_{I_t}$ to denote the reward received and the at time step $t$ and the distribution of the chosen arm $I_t$?

Isn't the distribution independent of the time the arm $i$ was chosen? Each one of the two references you describe assumes the context of the random bandit problem proposed by Robbins (1952) where ...
DeepQZero's user avatar
  • 1,399
2 votes

Why do we use $X_{I_t,t}$ and $v_{I_t}$ to denote the reward received and the at time step $t$ and the distribution of the chosen arm $I_t$?

Isn't the distribution independent of the time the arm $i$ was chosen? Yes, but you don't know which arm was chosen at time $t$, that is what $I_t$ represents. $v_i$ would represent the $i$th arms ...
David's user avatar
  • 4,920
2 votes
Accepted

How UCT in MCTS selection phase avoids starvation?

First explore the nodes A,B,C once. For reference see this paper by David Silver and Sylvain Gelly, Combining Online and Offline Knowledge in UCT If any action from the current state $s$ is not ...
Cohensius's user avatar
  • 413
1 vote
Accepted

UCB, Thompson sampling etc seems myopic/greedy for bandits?

The (binary) multi-armed bandit actually is a MDP with one state and $K$ actions. So your suggestion boils down to meta-learning: Find the parameters of one MDP that can solve another. Let's go with ...
maxy's user avatar
  • 233
1 vote

MCTS: How to select children when none of them are visited?

Unexplored children If a node has any unexplored children you have to select one of them, before computing UCB values and selecting the best one. Alternatively you could return ...
KarelPeeters's user avatar
1 vote

Difference in UCB performance when scaling the rewards

Epsilon greedy is unaffected by scaling of rewards, it always selects a random action with a probability of epsilon. On the other hand, if we look at the formulation of UCB (Section 2.7 of ...
James's user avatar
  • 241
1 vote
Accepted

What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?

Assigning a value of $\infty$ to unvisited nodes is indeed the "default" or most basic choice, and it indeed ensures that the search never visits a node for a second time if it also still ...
Dennis Soemers's user avatar
  • 10.3k
1 vote

In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?

The upper bound used here is derived from Hoeffding's inequality, which provides a symmetric, two-sided confidence interval. A good pair of blog posts on how this bound used in UCB for bandits is ...
Dennis Soemers's user avatar
  • 10.3k
1 vote

Multi Armed Bandits with large number of arms

Without any knowledge on the references you came across, I am assuming that the authors were considering common applications of MAB (planning, online learning, etc.) for which the time horizon is ...
rhdxor's user avatar
  • 206

Only top scored, non community-wiki answers of a minimum length are eligible