All Questions
Tagged with online-algorithms multiarmed-bandit
12 questions
0
votes
0
answers
14
views
Lower bound for stochastic bandits with short horizons
I want to show that if the horizon $n$ is strictly less than the number of arms $k$ then every algorithm enjoys a regret of at least
$$
\frac{n(2k-n-1)}{2k}
$$
Now, Lattimore and Szepesvári start from ...
- 133
3
votes
1
answer
54
views
Exact regret of $\epsilon$-greedy algorithm for $k$-armed bandit
The $\epsilon$-greedy algorithm for $k$-armed bandit, tosses a coin with success probability $\epsilon$ at each round and does the following:
If not successful chooses the best arm till now, and
if ...
- 133
0
votes
0
answers
22
views
Regret bound of epsilon-greedy algorithm for multi-armed bandit problem
Consider $1$-subgaussian MAB with $n\geq 2$, consider the $\epsilon$-greedy algorithm: First choose each arm once and subsequently choose $A_t=\arg\max \hat \mu_i(t-1)$ with pr. $1-\epsilon_t$ and ...
1
vote
1
answer
174
views
Understanding the regret bound of stochastic bandit vs. adversarial bandit
I am a beginner at MAB. One thing that puzzles me these days:
The regret of the UCB policy (and Thompson Sampling with no prior) for stochastic bandit is $\sqrt{KT\ln T}$, but the regret of the EXP3 ...
- 93
0
votes
1
answer
81
views
Big-O of Upperbound on the Regret of Exp3
I'm having difficulty understanding how to compute Big-O for the upper bound on the regret in Exp3 algorithm.
I think the actual algorithm isn't quite important for my question but since I couldn't ...
- 173
2
votes
1
answer
47
views
Strategy when introducing a new arm
Let's say we have a bandit with two arms, and we know that one arm has a reward probability 0.5 and the other is unknown. How do we create a strategy to maximise the reward?
- 21
3
votes
1
answer
653
views
Difference between regret and pseudo-regret definitions
I am following the book Bandit Algorithms. In page 48, they introduces regret after $n$ rounds as
$$
\mathbf{R} = n\mu^\star - \mathbb{E}\Bigg[\sum_{t=1}^n \mathbf{X}_t\Bigg] \tag{1}
$$
In page 55, ...
- 297
4
votes
1
answer
218
views
Bandit-like setup but taking max reward over sequential choices
Similar to my other question Bandit-like setup but taking max reward over multiple heads?, I'm interested in situations like the Multi-Armed Bandit setup, except where the reward is aggregated a ...
- 180
3
votes
1
answer
174
views
Bandit-like setting with maximum reward over multiple arms?
If I have a process where I can evaluate one of a number of options per 'round', with variable reward, and I want to maximise reward over time, the multi-armed bandit literature has lots of useful ...
- 180
2
votes
1
answer
450
views
Are Bandit Algorithms Considered as Online Algorithms?
I think bandit algorithms(such as multi-armed bandit algorithms) can be considered as online algorithms because they make decision and update the parameters as data arrives. However, I can't find any ...
- 1,027
4
votes
1
answer
374
views
What is the best strategy for the simplified version of the multi-armed bandit?
Consider a simplified version of the multi-armed bandit problem, where:
like in the standard multi-armed bandit: when you pull the lever of 1 bandit you win/lose some amount from that bandit
...
- 1,250
1
vote
1
answer
361
views
Doubt about definition of Regret in Online convex optimization setting
In online convex optimization, the regret of an algorithm $\mathcal{A}$ as defined in Introduction to Online Convex Optimization (Page 5) is:
$$
regret_T(\mathcal{A}) = \sup_{\{f_1,...,f_T\}} \sum_{t=...
