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
27 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?
user avatar
  • 11
0 votes
0 answers
17 views

How would we set the initial parameters of beta distribution of Thompson sampling if we want to start the model with the existing data?

This was one of the business-related questions from my technical interview last week for a data science position in a recommender system team at a search engine company focusing on advertisement ...
user avatar
  • 221
2 votes
1 answer
100 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 ...
user avatar
0 votes
1 answer
16 views

Best grouping rows method with Multi-Armed Bandit

I have a dataframe , here above a sample : ...
user avatar
  • 129
0 votes
0 answers
57 views

Are UCB, TS variants (LinUCB, LinTS) efficient for contextual bandits

WE can use UCB, Thompson sampling for MAB problems. Similarly, for contextual bandits, we can use LinUCB and LinTS. However, why doesnot the vowpal wabbit library support LinUCB, LinTS for exploration ...
user avatar
  • 717
2 votes
1 answer
48 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 ...
user avatar
1 vote
1 answer
27 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 ...
user avatar
2 votes
1 answer
99 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, ...
user avatar
  • 217
1 vote
1 answer
26 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 ...
user avatar
1 vote
0 answers
45 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 ...
user avatar
  • 11
2 votes
0 answers
78 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 ...
user avatar
  • 1,306
1 vote
0 answers
19 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 ...
user avatar
  • 111
1 vote
1 answer
35 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 ...
user avatar
  • 1,306
1 vote
0 answers
37 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,...
user avatar
0 votes
0 answers
25 views

How do I reconcile a flipped sign in the Hoeffding's inequality derivation of UCB?

In the language of bandit theory, let's suppose we have some action value $q(a)$ which is the expected value of the reward yielded from choosing action $a$. We also have some estimate of what $q(a)$ ...
user avatar
  • 133
0 votes
0 answers
36 views

statistical tests for multi-armed bandit strategies

Assuming that I have 2 strategies (X and Y) for a contextual multi-armed bandit problem. I want to perform a statistical test for determining which of the two strategies yields the highest reward. ...
user avatar
  • 11
0 votes
1 answer
62 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 ...
user avatar
  • 101
4 votes
1 answer
92 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 ...
user avatar
  • 180
3 votes
1 answer
64 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 ...
user avatar
  • 180
2 votes
1 answer
87 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 ...
user avatar
  • 419
1 vote
0 answers
14 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 ...
user avatar
0 votes
1 answer
42 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 ...
user avatar
6 votes
0 answers
112 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 ...
user avatar
  • 181
1 vote
1 answer
74 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 ...
user avatar
  • 479
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 ...
user avatar
  • 155
4 votes
1 answer
90 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 ...
user avatar
  • 49
2 votes
1 answer
54 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 ...
user avatar
  • 131
0 votes
0 answers
39 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 ...
user avatar
  • 1
0 votes
1 answer
74 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 ...
user avatar
  • 3
1 vote
1 answer
224 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 ...
user avatar
2 votes
1 answer
146 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 ...
user avatar
  • 643
2 votes
2 answers
244 views

Why does greedy algorithm for Multi-arm bandit incur linear regret?

I am watching David silver's course on Exploration and Exploitation, in the lecture he explains the greedy algorithm for multi - arm bandit in the following manner: Estimate $Q_t(a)$ for each arm by ...
user avatar
  • 876
0 votes
1 answer
157 views

Intuition behind Thompson Sampling in Reinforcement Learning

I am trying to get intuition for solving bandit problem using Thompson Sampling in Reinforcement Learning. I understand following: Beta distribution and effect of alpha and beta params on it Thompson ...
user avatar
0 votes
1 answer
108 views

How to evaluate/interprete success fail for beta distribution

Imagine we have two-armed Bandit with the prior binary distribution. How can we interpret that using beta distribution? meaning: which arm is the best arm to chose based on the prior? arm 1: 5 ...
user avatar
  • 103
3 votes
1 answer
221 views

Difference between MABs and full MDPs

As far as Im aware, the difference between Multi-armed Bandit problems and full MDPs is that in MABs the full distribution over the results of action are known. Is this true?
user avatar
  • 41
0 votes
0 answers
92 views

Are $\alpha, \beta$ of Beta distribution positive integer inn Thompson Sampling

In wikipedia on beta distribution, they say that domain of hyperparameter $\alpha, \beta$ are positive real numbers. However, according to my reasons, the domain of $\alpha, \beta$ should be limited ...
user avatar
5 votes
1 answer
138 views

Equivalence of Contextual Bandit formulations

I find two different type of Contextual Bandit problem formulations in the literature: Definition 1: (https://hunch.net/~jl/projects/interactive/sidebandits/bandit.pdf) In a contextual bandits problem,...
user avatar
0 votes
0 answers
18 views

Linear Thompson sampling - non linear relations dominate sampled rewards

I'm implementing linear Thompson sampling for a project. I am simulating random features with rewards that are linear related to some features them and non linear to others. For the non linear ...
user avatar
  • 479
4 votes
2 answers
504 views

What is the relationship between Boltzmann / Gibbs sampling and the softmax function?

I'm looking at sampling functions in the context of reinforcement learning; specifically the explore/exploit problem. A method I've seen pretty often is to derive the action by assigning a score to ...
user avatar
  • 1,509
3 votes
1 answer
194 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 ...
user avatar
  • 1,048
0 votes
1 answer
63 views

How is Regret defined for combinatorial optimization problems?

I have a combinatorial optimization problem, where I'm trying to find the global minimum (many local minima exist) In principle, my agent can choose to be anywhere in the state space at any given ...
user avatar
1 vote
1 answer
169 views

What Does Oracle in Multi-Armed Bandit Literatures?

Often encounter "oracle" this term in multi-armed bandit literatures. But none of papers explain what that means. An example: Practical Contextual Bandits with Regression Oracles
user avatar
  • 643
3 votes
1 answer
293 views

How to Deploy Contextual Bandits in Online Experimentation Platform?

This question is about how to deploy contextual bandits(CMAB) in the context of web site optimization and online experimentation. I implemented contextual free MAB(MAB). When I run a MAB experiment, I ...
user avatar
  • 643
12 votes
2 answers
626 views

Etymology of multi-armed bandit

I'm studying Reinforcement Learning, and have come across multi-armed bandits. Why are these called bandits? And why are they armed?
user avatar
  • 2,261
3 votes
1 answer
111 views

States in Bandit Problems

I am wondering if there is an interpretation of the Bandit Problem with more than one states. I know that there are versions which views each slot machine as an independent Markovian machines and as ...
user avatar
2 votes
1 answer
1k views

Gradient Bandit Algorithm

I read about the Gradient Bandit Algorithm as a possible solution to the Multi-armed Bandits, and I didn’t understand it. I would be happy if anyone can send me a link to a video, blog post, book, ...
user avatar
  • 67
3 votes
1 answer
32 views

A small adjustment to the Multi-Armed Bandit problem

What class of problems does this belong to: Similar to multi-armed bandit, but with a small adjustment/difference: by choosing an action at every time step you not only receive the reward of that ...
user avatar
1 vote
1 answer
135 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=...
user avatar
2 votes
1 answer
96 views

Mechanism of Adversarial Multi-Armed Bandit Problem?

I am studying the Bandit Algorithms book by Tor Lattimore and Csaba Szepesv´ari and I have studied the adversarial bandit problem. However, I don't understand what is the mechanism of adversarial ...
user avatar
  • 501
3 votes
2 answers
128 views

Contextual bandits: Number of models to estimate

I have recently read several papers on contextual bandits especially for the case of binary rewards. However, one very basic aspect is not entirely clear to me: In some papers (e.g. here https://arxiv....
user avatar
  • 31