# 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.

186 questions
Filter by
Sorted by
Tagged with
1 vote
16 views

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 ...
• 121
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 ...
• 693
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 ...
• 1,230
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 ...
• 425
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 ...
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 ...
• 265
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 ...
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 ...
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 ...
• 1,015
1 vote
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 ...
1 vote
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 ...
• 123
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 ...
• 101
1 vote
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 ...
• 93
57 views

• 331
1 vote
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?-- ...
• 165
1 vote
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 ...
• 73
1 vote
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 ...
• 183
1 vote
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/...
• 11
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 ...
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 ...
• 151
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?
• 21
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 ...
18 views

### Best grouping rows method with Multi-Armed Bandit

I have a dataframe , here above a sample : ...
• 249
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 ...
• 207
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 ...
• 309
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, ...
• 297
1 vote
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 ...
1 vote
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 ...
• 11
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 ...
• 2,245
1 vote
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 ...
• 111
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 ...
• 2,245
1 vote
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,...
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 ...
• 101
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 ...
• 180
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 ...
• 180
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
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 ...
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 ...
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 ...
• 183
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 ...
• 521
1 vote
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
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 ...
• 59
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 ...