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
4
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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. ...
0
votes
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 ...
0
votes
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 ...
6
votes
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 ...
2
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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?
0
votes
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 ...
0
votes
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 ...
5
votes
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,...
0
votes
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 ...
4
votes
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 ...
3
votes
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 ...
0
votes
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 ...
0
votes
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
3
votes
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 ...
11
votes
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?
2
votes
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 ...
2
votes
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, ...
3
votes
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 ...
1
vote
1answer
78 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=...
2
votes
1answer
56 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 ...
2
votes
2answers
86 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....
0
votes
1answer
107 views

A/B testing and Multi-armed bandit algorithms in a recommender system

I was reading about these two algorithms, but I don't understand how they can be used in a recommender system because using the MovieLens dataset these algorithms recommend the best movie for all the ...
1
vote
1answer
39 views

Calclulation of epoch length in UCB2

I am trying to understand the UCB2 algorithm presented in [1]. In step 2 of the algorithm, it says : Play machine j exactly $\tau(r_j+1) - \tau(r_j)$ times, where $\tau(r_j) = \lceil (1+\alpha)^{...
1
vote
1answer
83 views

Multi armed bandits with natural ordering between bandits

Say I have a button in my website that I want to optimize the size given some metric. In order to use multi armed bandits for that, there are some things I would like to consider: My metric is a ...
1
vote
1answer
161 views

What is the intuition behind the fact that the Explore Then Commit algorithm in a multiarmed bandit problem can achieve sublinear regret?

The thing that confuses me is as follows: no matter how many times we explore each arm at the beginning, there is some chance that the arm that performed the best on the sample is actually a ...
3
votes
1answer
617 views

UCB Exploration in Reinforcement Learning

I have two questions regarding the upper confidence bounds (UCB) exploration in reinforcement learning: UCB exploration is derived from Hoeffding's inequality which assumes that the reward is bounded ...
0
votes
1answer
61 views

How does Thomson Sampling work in a real world application of Multi Armed Bandit Testing

I understand the basics of Thomson Sampling, but how is it implemented in practice? If there are three variants each with a 1/3 of traffic allocated to them on day 1, how is traffic dynamically ...
0
votes
1answer
31 views

way to transform reinforcement learning problems to bandit problems

I wonder what a general way looks like to transform reinforcement learning problems to bandit problems (especially contextual bandit problems) Thank you!
2
votes
1answer
281 views

Using IPS(inverse probability weighting) with a deterministic policy as the logging policy

In a contextual bandit problem, why can't we use inverse probability weighting (inverse propensity score) with a deterministic policy as the logging policy? Could you give me a concrete example?
0
votes
1answer
110 views

Policy evaluation in contextual bandit setting

I am currently reading a paper whose links is (Exploration Scavenging) http://delivery.acm.org/10.1145/1400000/1390223/p528-langford.pdf?ip=128.135.98.49&id=1390223&acc=ACTIVE%20SERVICE&...
0
votes
1answer
95 views

quick questions about a contextual bandit problem

I am currently reading the paper "Learning from Logged Implicit Exploration Data" https://arxiv.org/pdf/1003.0120.pdf. But I believe the questions I have can be answered without reading the whole ...
3
votes
1answer
62 views

What does this logarithmic decay schedule mean?

In the context of minimizing regret among $\varepsilon$-greedy strategies for a multi-armed bandit problem, a number of sources* present the following decay schedule with a claim that it has ...
0
votes
1answer
288 views

How do we calculate regret or know best action in a multi armed bandit at run time in a program(python)?

Consider $K$ arms, each having a normal distribution with mean $\mu_k$ taken from: $$\mu_k ∼ \mathbb{N}(0,1)$$ Then, the reward function $R_t(\mu_k)$ at time $t$ has distribution: $$R_t(\mu_k) ∼ \...
0
votes
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. ...
0
votes
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. ...
1
vote
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 ...