Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
55 views

RL agent focusses too much on early rewards, even with no discounting

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 ...
2 votes
1 answer
78 views

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

When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep. ...
0 votes
1 answer
335 views

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

I am trying to implement MCTS for a custom word game I am working on. I feel like I have got all the pieces of code needed, but the algorithm seems to always return the first available move (first ...
5 votes
1 answer
877 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 ...
2 votes
1 answer
604 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 ...
5 votes
1 answer
578 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 ...
3 votes
3 answers
727 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 ...
3 votes
1 answer
538 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}},...
1 vote
0 answers
248 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 ...
2 votes
1 answer
496 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 ...
5 votes
1 answer
1k 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: ...
4 votes
2 answers
120 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)...
2 votes
0 answers
666 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 ${...
4 votes
1 answer
572 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 ...
1 vote
1 answer
559 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{ \...
4 votes
2 answers
2k 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 ...
1 vote
1 answer
3k 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 ...