Questions tagged [upper-confidence-bound]
For questions about the upper confidence bound (UCB)-based algorithms or action selection strategies in the context e.g. of bandit or reinforcement learning problems.
16
questions
0
votes
0
answers
26
views
UCB algorithm exercise
I am trying to understand the UCB algorithm and I'm trying to understand it using an exercise. Here's the Upper Confidence Bound algorithm explanation:
Now I have the following exercise: Suppose we ...
- 113
0
votes
0
answers
15
views
How is the union bound being used?
I am trying to understand the assumption proof of Theorem 2(Page -$7$) in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Inequality 1
\begin{align}
\mathbb{...
- 111
2
votes
1
answer
264
views
Difference in UCB performance when scaling the rewards
I notice the following behavior when running experiments with $\epsilon$-greedy and UCB1. If the reward is kept binary (0 or 1) both algorithm's performances are on par with each other. However, if I ...
- 223
5
votes
1
answer
232
views
In MCTS, what to do if I do not want to simulate till the end of the game?
I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS ...
- 53
3
votes
1
answer
286
views
How UCT in MCTS selection phase avoids starvation?
The first step of MCTS is to keep choosing nodes based on Upper Confidence Bound applied to trees (UCT) until it reaches a leaf node where UCT is defined as
$$\frac{w_i}{n_i}+c\sqrt{\frac{ln(t)}{n_i}},...
- 667
1
vote
0
answers
127
views
UCB-like algorithms: how do you compute the exploration bonus?
My question concerns Stochastic Combinatorial Multiarmed Bandits. More specifically, the algorithm called CombUCB1 presented in this paper. It is a UCB-like algorithm.
Essentially, in each round of ...
- 11
5
votes
1
answer
523
views
What should the initial UCT value be with MCTS, when leaf's simulation count is zero? Infinity?
I am implenting a Monte Carlo Tree Search algorithm, where the selection process is done through Upper Confidence Bound formula:
...
- 153
2
votes
1
answer
295
views
In UCB, is the actual upper bound an upper bound of an one-sided or two-sided confidence interval?
I'm a bit confused about the visualization of the upper bound (following the notation of (c.f. Sutton & Barto (2018))
$$Q_t(a)+C\sqrt{\frac{\mathrm{ln}(t)}{N_t(a)}}$$
In many blog posts about the ...
- 101
5
votes
1
answer
559
views
Multi Armed Bandits with large number of arms
I'm dealing with a (stochastic) Multi Armed Bandit (MAB) with a large number of arms.
Consider a pizza machine that produces a pizza depending on an input $i$ (equivalent to an arm). The (finite) set ...
- 101
2
votes
0
answers
224
views
Why is the ideal exploration parameter in the UCT algorithm $\sqrt{2}$?
From Wikipedia, in the Monte-Carlo Tree Search algorithm, you should choose the node that maximizes the value:
$${\displaystyle {\frac {w_{i}}{n_{i}}}+c{\sqrt {\frac {\ln N_{i}}{n_{i}}}}},$$
where
${...
- 21
3
votes
3
answers
280
views
Why aren't exploration techniques, such as UCB or Thompson sampling, used in full RL problems?
Why aren't exploration techniques, such as UCB or Thompson sampling, typically used in bandit problems, used in full RL problems?
Monte Carlo Tree Search may use the above-mentioned methods in its ...
- 321
4
votes
1
answer
283
views
Why do we have two similar action selection strategies for UCB1?
In the literature, there are at least two action selection strategies associated with the UCB1's action selection strategy/policy. For example, in the paper Algorithms for the multi-armed bandit ...
- 36.4k
4
votes
2
answers
118
views
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$?
I'm doing some introductory research on classical (stochastic) MABs. However, I'm a little confused about the common notation (e.g. in the popular paper of Auer (2002) or Bubeck and Cesa-Bianchi (2012)...
- 41
1
vote
1
answer
2k
views
Why am I getting better performance with Thompson sampling than with UCB or $\epsilon$-greedy in a multi-armed bandit problem? [closed]
I ran a test using 3 strategies for multi-armed bandit: UCB, $\epsilon$-greedy, and Thompson sampling.
The results for the rewards I got are as follows:
Thompson sampling had the highest average ...
- 11
3
votes
2
answers
1k
views
Should I use exploration strategy in Policy Gradient algorithms?
In policy gradient algorithms the output is a stochastic policy - a probability for each action.
I believe that if I follow the policy (sample an action from the policy) I make use of exploration ...
- 165
1
vote
1
answer
266
views
How do we reach at the formula for UCB action-selection in multi-armed bandit problem?
I came across the formula for Upper Confidence Bound Action Selection (while studying multi-armed bandit problem), which looks like:
$$
A_t \dot{=} \operatorname{argmax}_a \left[ Q_t(a) + c \sqrt{ \...
- 147