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'$ ...
- 2,426
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 ...
- 39.6k
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-...
- 10.1k
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$ ...
- 2,336
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 ...
- 722
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 ...
- 1,126
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, ...
- 30.3k
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$ ...
- 21
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 ...
- 1,282
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 ...
- 4,665
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 ...
- 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 ...
- 223
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 ...
- 373
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 ...
- 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 ...
- 10.1k
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 ...
- 10.1k
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 ...
- 206
Only top scored, non community-wiki answers of a minimum length are eligible