Questions tagged [multiarmed-bandit]
A problem in which a fixed limited set of resources must be allocated between competing (alternative) choices in a way that maximizes their expected gain, when each choice's properties are only partially known at the time of allocation.
183
questions
0
votes
0
answers
57
views
Formal Bayes rule for the bandit problem
We have two slot machines, $B_1$ and $B_2$. We've played the first machine $n_1$ times and gotten the rewards $R_1^1, \dots, R_1^{n_1}$ and played the second machine $n_2$ times and gotten the rewards ...
- 195
2
votes
1
answer
39
views
Do Bernoulli bandits need a different treatment if the rewards are sparse?
I have a problem where, effectively, my slot machines have very low payout probability (on the order of 1% for the "best" slot machines) and my goal is to minimize the number of actions to ...
- 579
0
votes
0
answers
24
views
Unexpected Seasonal Pattern when Comparing Empirical Probability with Hoeffding's Inequality
I am visualizing the difference between the empirical probability and the theoretical upper bound of the deviation of the sample mean from the true mean of successive Bernoulli trials. I'm using ...
0
votes
0
answers
19
views
The impact of allowing the reward to be negative in a contextual bandit problem
It seems the contextual bandits problems, as shown in these two papers Tong Mu, Yash Chandak, Tatsunori Hashimoto, Emma Brunskill: Factored DRO: Factored Distributionally Robust Policies for ...
- 945
1
vote
1
answer
64
views
Extending Bernoulli thompson sampling for slate bandit problems to the contextual setting
I am trying to implement the extension to Marginal Posterior Sampling for Slate Bandits, which is a context-free slate bandit algorithm that uses Thompson sampling with a Bernoulli prior.
I want to ...
- 479
1
vote
0
answers
24
views
Equivalent Formulations of Thompson Sampling
I am studying Chapter 36 Thompson Sampling of the book Bandit Algorithms by Lattimore and Szepesvari. The authors present two equivalent formulations of Thompson Sampling on page 460, and I am having ...
- 123
0
votes
1
answer
43
views
Thompson Sampling with Two objectives - Cost and Success Rate
I have implemented a Thompson sampling algorithm with beta distribution that chooses between two processors to process the payments for each transaction such that it maximizes the success rate. For ...
- 101
0
votes
0
answers
28
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 ...
- 81
1
vote
1
answer
23
views
Trying to reproduce proof of Bandit Gradient Algorithm as SGD
I'm trying to make sense of the "The Bandit Gradient Algorithm as Stochastic Gradient Ascent" proof in Sutton and Barto's intro to RL textbook. I'm stuck on the line
$E[(q_*(A_t)-B_t)\frac{\...
- 11
1
vote
1
answer
223
views
Difference between Bayesian optimization and multi-armed bandit optimization
What are the differences between Bayesian optimization and multi-armed bandit optimization? Are the problems equivalent when multi-armed bandit's action space is infinite?
- 2,416
2
votes
1
answer
32
views
Multi-armed bandit with max instead of mean
Is there a term or name (or better yet, strategies) for the following problem?
Take a 'standard' $k$-armed multi-armed bandit problem (stochastic real rewards, IID pulls for a given arm), but instead ...
- 313
0
votes
0
answers
98
views
Multi-armed bandit with time series
Suppose that I have a multi-armed bandit problem: I am trying to set the price of a product, and each arm corresponds to one choice of the price. I pulled one arm and observe the corresponding revenue....
- 155
0
votes
1
answer
31
views
Context vector with norm 1
Very often in the literature authors state something like: "We consider a contextual linear bandit problem where at each round t, the learner receives a context vector $x_t \in R^d$ with norm 1&...
- 223
0
votes
1
answer
45
views
Bandit learning with biased and unbiased data
I have an online experimentation setup with incoming customers split into 3 groups:
Random (all arms are applied equally) 20%
Model-based (an existing, optimal strategy is run) 40%
MAB (Multi-armed ...
0
votes
1
answer
43
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
0
votes
0
answers
25
views
How is it possible to derive a bound on the difference between optimal action and current action in multi-armed bandit problem?
Suppose there is a linear bandit where the average reward is modeled as $r=\theta_*^\top x$ where $x$ shows the action in $\mathbb{R}^d$.In bandit algorithm, we usually find a confidence interval for ...
- 643
2
votes
0
answers
42
views
Estimating probability of superiority in an A/B test with multinomial outcomes
Let's say I have an A/B (/C etc.) test, where the outcome of each trial is draw from a multinomial distribution with unknown frequencies. Each possible outcome value $x_i$ has a specified utility, $...
- 321
1
vote
1
answer
253
views
Difference between Epoch-greedy and Epsilon-Greedy algorithm for contextual bandits
I am trying to compare Epoch Greedy in Langford & Zhang's paper and the epsilon-greedy approach for contextual bandits as in Chen et al, 2020. My question is that are these the same algorithms?-- ...
- 165
1
vote
1
answer
104
views
Minimum sampling for maximising the prediction accuracy [closed]
Suppose that I'm training a machine learning model to predict people's age by a picture of their faces. Lets say that I have a dataset of people from 1 year olds to 100 year olds. But I want to choose ...
- 73
1
vote
0
answers
36
views
How to solve this type of multi-task Bayesian optimization problem?
Let us consider a collection of local Bayesian optimization tasks, each employs a Gaussian Process model to find the local optimum (i.e. global optimum of that task). The goal is to design a ...
- 173
1
vote
0
answers
69
views
Data Imbalance in Contextual Bandit with Thompson Sampling
I'm working with the Online Logistic Regression Algorithm (Algorithm 3) of Chapelle and Li in their paper, "An Empirical Evaluation of Thompson Sampling" (https://papers.nips.cc/paper/2011/...
- 11
5
votes
1
answer
181
views
How do find the best arm in a multi-armed bandit when exploitation is unimportant?
I have a problem similar to the 'Bernoulli bandit' problem in the exploration-exploitation paradigm, but without the exploitation element.
In particular, I have many levers that I can pull and each ...
- 155
2
votes
1
answer
230
views
Understanding percentage of optimal action in Reinforcement Learning
I'm new Reinforcement learning and currently reading Sutton & Barto's book "Reinforcement Learning: An Introduction". In Chapter 2, they compare greedy and non-greedy methods on 10-armed ...
- 151
2
votes
1
answer
45
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
2
votes
1
answer
195
views
Learning payoffs from variable number of armed bandits
Does there exist a technique, such that while computing the returns of multi-armed bandits, we have the possibility of introducing an extra bandit? If the number of bandits was fixed, we could ...
- 572
0
votes
1
answer
17
views
Best grouping rows method with Multi-Armed Bandit
I have a dataframe , here above a sample :
...
- 239
4
votes
1
answer
211
views
Multi-armed bandit algorithm for finding the best performing bandit in the least amount of trials
I'm wondering if there's an algorithm that minimizes the expected posterior loss for the best performing bandit where regret is calculated as the number of trials to achieve a threshold for posterior ...
- 207
1
vote
1
answer
88
views
Multi-armed bandit - how does the gambler choose what's the best strategy?
In the multi-armed bandit problem, I would like to clarify exactly what happens from time step $t=1$ in the context of the epsilon greedy strategy for $\epsilon=0$ and $0<\epsilon \leq 1$. By what ...
- 167
2
votes
1
answer
475
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, ...
- 247
1
vote
1
answer
93
views
In reinforcement learning/multi-armed bandits, why do we look at expected reward and not the most likely reward? [duplicate]
This is the dilemma that I have faced in applied probability in general. Say you have the choice to put your savings of $\$10$ in a deposit account with guaranteed retun of $\$100$ or buy a lottery ...
- 23
1
vote
0
answers
99
views
Why do linear bandits use ridge regression to estimate parameters?
I’m implementing an adaptive experimental design where arms are assigned according to the posterior probability that they are the best arm. I’ve noticed in several articles that people use ridge ...
- 11
3
votes
0
answers
425
views
Thompson sampling when the reward is not simply one
I am trying to implement a simple simulation of Thompson sampling for pricing inspired by Python code from here. Another very similar/realted post can be found here.
The idea is that I have different ...
- 1,987
1
vote
0
answers
108
views
Can Thomson sampling be used for better results in a 1 player-MCTS
I made a Monte Carlo tree search (MCTS) algorithm for the travelling salesman problem inspired by this paper which uses UCB1.
When I was digging to see where does the UCB1 formula comes from, I read ...
- 111
2
votes
1
answer
89
views
does Thompson sampling for price optimisation require discriminative pricing
I get the gist of Thompson sampling for price optimisation (I think - see this video around minute 31). I wonder, would Thompson sampling require discriminative pricing or can prices be change ...
- 1,987
1
vote
0
answers
39
views
Binomial riddle [closed]
I have a riddle that i cannot solve:
I'm a recruiter searching for the best basketball player in a town. There are 100 candidates in the town. 99 of them have a probability of basket the ball of 0.501,...
- 11
0
votes
1
answer
129
views
Risk-averse multi-armed bandits
We want to pose one problem as a multi-armed bandit setting. The issue is that some of the arms are very risky with potentially undesirable effects (or not). Is there a way to do a risk-aware ...
- 101
4
votes
1
answer
198
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
112
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
3
votes
2
answers
1k
views
Real-World, Operationalized Applications of Multi-Arm Bandits
Multi-armed bandits are wonderful and have lots of potential applications. However, I don't know many companies or real-world practitioners who have implemented bandit algorithms.
What are some ...
- 489
1
vote
0
answers
19
views
Nonstationary and stationaryProblem [closed]
What is the difference between these formulas because I am confused with the difference between them, from what I understand is that the first equation is for stationary situation, while the second ...
0
votes
1
answer
62
views
Multi-armed Bandits
Could someone explains to me the notation of this function, I mean I understand that we take the average of sum of the rewards for some particular action, however the notation seems strange to me for ...
6
votes
0
answers
266
views
Confidence Interval for least squares estimator
There was a paper by Yasin-Abbasi-Yadkori https://arxiv.org/pdf/1102.2670.pdf titled Online Least Squares Estimation with Self-Normalized Processes. I am trying to give a brief context before asking ...
- 183
2
votes
1
answer
114
views
Batches of bayesian updates for gaussian with unknown variance different from computation with all data
I'm working on a project where I continuously (in batches) update the pdf estimation for an event normally distributed. My variance is unknown, so I'm using the equations given in session 4.1.2 of ...
- 521
1
vote
0
answers
7
views
Finding winner of the competition with give minimum probability by giving method that can carry out each game of the competition
I came across the following problem:
Consider a competition in which a game is played between two participants. There are total $n$ participants. Let $p_{ij}$ represent participant $i$ will beat ...
- 205
5
votes
1
answer
136
views
How many samples are needed to distinguish the means of two distributions in multi-armed bandits?
In a paper on Multi Armed Bandits, I came across the following statement:
This generalizes the well-known fact that one needs of order $\frac{1}{\Delta^2}$ samples to differentiate the means of two ...
- 59
2
votes
1
answer
78
views
Estimating rewards for coin flip game, given the bias of the coin but not the outcome of the flip
I perform a series of $N$ coin flips, indexed $i = 1, \ldots, N$. I do not get to see the outcome of the coin flips, but for each one I know the probability of the coin being heads, $p_i(H)$. This ...
- 131
0
votes
0
answers
108
views
How to derive Chernoff Bounds for Sample Variance?
I was reading a paper on Bandits where I encountered this:
After searching around on the internet I found and understood the first set of bounds quite well. However, I could not find any explanation ...
- 1
0
votes
1
answer
115
views
Bayesian number guessing [closed]
This is a personal learning exercise:
Suppose an agent knows the range of values that a number (N) can take but is only given feedback about how right or wrong he is after he makes a guess (os given ...
- 3
1
vote
1
answer
400
views
Thompson sampling with Bernoulli prior and non-binary reward update
I am solving a problem for which I have to select best possible server(level 1) to hit for a given data. These server(level 1) in turn hit some other servers(level 2) to complete the request. The ...
2
votes
1
answer
285
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 ...
- 887