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

149 questions
Filter by
Sorted by
Tagged with
0answers
34 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 ...
1answer
67 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 ...
0answers
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 ...
0answers
7 views

### MAB with Depdendent Variants

I'm currently running a multi-armed bandit to select the best email subject based on email click rate. I was hoping to extend the MAB to also encompass the email copy and test out all the variants. ...
0answers
21 views

### Normal Conjugate Normal Inverse-gamma Updating

I am attempting to code a multi-arm bandit where there are multiple variants that can be served to customers with the objective of learning the best one based on an outcome modeled with a normal ...
0answers
14 views

### Multi Arm Bandits - Purchase Amount Zero Inflated

All the examples I have seen for multi-arm bandits (MAB) applied to say online advertising are for cases where the reward is binary (e.g. click, no click) or continuous (e.g. assuming a normal ...
1answer
69 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 ...
1answer
43 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 ...
0answers
31 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 ...
1answer
59 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 ...
0answers
46 views

### Repeated Multi-armed bandit trails of pure exploration: Bernoulli arms

I'm interested in analyzing a variant of the multi-armed bandit problem with pure exploration. In this variant, in each round we receive samples from two distributions and we need to estimate which ...
1answer
126 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 ...
0answers
24 views

### Strategic Multi Armed Bandit

As a part of my project, I have been tasked with formulating a multi-armed bandit problem with strategic arms. What I have found out is a Gittin's index approach to the problem provides a solution ...
1answer
104 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 ...
2answers
64 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 ...
0answers
22 views

### Is there a UCB type algorithm for linear stochastic bandit with lasso regression?

Why is there no upper confidence bound algorithm for linear stochastic bandits that uses lasso regression in the case that the regression parameters are sparse in the features? In particular, I don't ...
1answer
87 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 ...
1answer
57 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 ...
1answer
105 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?
0answers
46 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 ...
0answers
22 views

### Which variant should be selected at the end of a multi-armed bandit(MAB) test?

The question is in the context of online experimentation, i.e. A/B testing. I understand we can use MAB testing to maximize conversions during a test window. But if we want to select a variant to be ...
1answer
110 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,...
0answers
14 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 ...
2answers
257 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 ...
1answer
83 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 ...
1answer
47 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 ...
1answer
81 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
1answer
131 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 ...
2answers
496 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?
1answer
53 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 ...
1answer
146 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, ...
1answer
26 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 ...
1answer
78 views

0answers
29 views

### Multi-armed Bandit Algorithm selection and Optimization

I have 2 channels that I can sent my products, the A channel cost 0.10\$per product and the B costs 0.01\$ and I am trying dynamically to optimize the channel selection by minimize the cost. ...
1answer
716 views

### Multi-armed bandit epsilon greedy

This is the code from a lecture from the Artificial Intelligence Reinforcement Learning in Python course on Udemy to implement the multi-armed bandit epsilon greedy. ...
0answers
41 views

### EXP4 algorithm: Changes in exponential weight update rule for multiple arms?

I am new to contextual MAB problems so I have a few doubts. I am trying to implement the EXP4 algorithm, however in EXP4 we only choose one arm at a time based on the advice of the Experts. We then ...