Skip to main content

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
16 views

Adding of Baseline parmter in derivation of Gradient Bandit Algorithm

In the derivation of the Gradient Bandit Algorithm in Chapter 2.8 of the Reinforcement Learning book by Sutton & Barto they introduce a introduce a baseline term $B_t$ and I can't seem to figure ...
Rafay Khan's user avatar
0 votes
0 answers
24 views

How to derive instant-dependent regret for KL-UCB bandit?

I was reading KL-UCB algorithm for bandit with Bernoulli reward from Bandit Algorithms book by Lattimore (Section 10.2), and the regret provided by the algorithm is instant-dependent and it depends on ...
Amin's user avatar
  • 693
3 votes
1 answer
100 views

Multi-armed bandit with 2 coins: What strategy maximises reward?

What strategy maximises the total reward, on average, after $n$ trials, in this multi-armed bandit: two coins A and B, with probability of success $p_A$ and $p_B$ reward is $1$ on success, $0$ on ...
elemolotiv's user avatar
  • 1,230
0 votes
0 answers
10 views

Methods for discriminating between Markov kernels

I'm interested in problems of the following form, which I've deliberately specified a bit vaguely. I would like to know if problems of this kind have been studied, and if so what they're called and ...
N. Virgo's user avatar
  • 425
0 votes
1 answer
58 views

How to compute Upper Confidence Bound Properly In Multiarmed Bandit Problem

I'm currently working on implementing the Upper Confidence Bound (UCB) algorithm for the Multiarmed Bandit Problem, but I'm encountering some difficulties with the computation. Here's what I've ...
mehruddin's user avatar
0 votes
0 answers
63 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 ...
Oskar's user avatar
  • 265
2 votes
1 answer
54 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 ...
Alexander Soare's user avatar
0 votes
0 answers
26 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 ...
Felipe Vieira's user avatar
0 votes
0 answers
22 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 ...
Hans's user avatar
  • 1,015
1 vote
1 answer
101 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 ...
Lucidnonsense's user avatar
1 vote
0 answers
25 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 ...
Extrava's user avatar
  • 123
0 votes
1 answer
106 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 ...
Aayush Gupta's user avatar
1 vote
1 answer
109 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 ...
zxzx179's user avatar
  • 93
2 votes
1 answer
57 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{\...
fyzr's user avatar
  • 21
1 vote
1 answer
659 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?
fool's user avatar
  • 2,480
2 votes
1 answer
46 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 ...
TLW's user avatar
  • 313
0 votes
1 answer
32 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&...
amarchin's user avatar
  • 223
0 votes
1 answer
70 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 ...
Tuan Minh Nguyen Hoang's user avatar
0 votes
1 answer
75 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 ...
Rowing0914's user avatar
2 votes
0 answers
45 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, $...
user1502040's user avatar
1 vote
1 answer
345 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?-- ...
user111092's user avatar
1 vote
1 answer
111 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 ...
noone's user avatar
  • 73
1 vote
0 answers
44 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 ...
Shaun Han's user avatar
  • 183
1 vote
0 answers
80 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/...
MABQ's user avatar
  • 11
5 votes
1 answer
301 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 ...
Oscar Cunningham's user avatar
2 votes
1 answer
378 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 ...
xabush's user avatar
  • 151
2 votes
1 answer
46 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?
Zuz's user avatar
  • 21
2 votes
1 answer
364 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 ...
desert_ranger's user avatar
0 votes
1 answer
18 views

Best grouping rows method with Multi-Armed Bandit

I have a dataframe , here above a sample : ...
user17241's user avatar
  • 249
4 votes
1 answer
256 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 ...
mihagazvoda's user avatar
2 votes
1 answer
112 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 ...
Slim Shady's user avatar
3 votes
1 answer
570 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, ...
Shew's user avatar
  • 297
1 vote
1 answer
99 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 ...
Abhay Gupta's user avatar
1 vote
0 answers
117 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 ...
Yrv88's user avatar
  • 11
4 votes
0 answers
483 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 ...
cs0815's user avatar
  • 2,245
1 vote
0 answers
130 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 ...
Butanium's user avatar
  • 111
2 votes
1 answer
96 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 ...
cs0815's user avatar
  • 2,245
1 vote
0 answers
48 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,...
wanttoknow's user avatar
0 votes
1 answer
147 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 ...
d56's user avatar
  • 101
4 votes
1 answer
213 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 ...
Oly's user avatar
  • 180
3 votes
1 answer
133 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 ...
Oly's user avatar
  • 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 ...
ABC's user avatar
  • 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 ...
Mohammed AL-Nashriy's user avatar
0 votes
1 answer
65 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 ...
Mohammed AL-Nashriy's user avatar
6 votes
0 answers
288 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 ...
rostader's user avatar
  • 183
2 votes
1 answer
125 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 ...
jcp's user avatar
  • 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 ...
Rnj's user avatar
  • 205
5 votes
1 answer
153 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 ...
D. B.'s user avatar
  • 59
2 votes
1 answer
85 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 ...
jdizzle's user avatar
  • 131
0 votes
0 answers
128 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 ...
Fahim's user avatar
  • 1