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
1answer
58 views

Multi-armed bandit simplified - what is the best strategy?

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
35 views
+50

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
0answers
14 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
0
votes
0answers
18 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 ...
8
votes
2answers
422 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?
1
vote
0answers
29 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 ...
1
vote
0answers
25 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
20 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 ...
0
votes
0answers
28 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=...
0
votes
0answers
28 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 ...
0
votes
0answers
18 views

Epsilon Thompson Sampling

Does it make sense to have the following variant of Thompson Sampling? e % of time doing exploration and (1-e) % of time doing regular Thompson Sampling. If this has been proposed by some papers, ...
2
votes
1answer
59 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
50 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
30 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)^{...
0
votes
0answers
24 views

Multi armed bandits with Thompson sampling and unknown rewards distribution

I have machine learning models that have a some possible post processing possibilities. I would like to use multi armed bandits to select the post processing that optimizes a continuous KPI. I have ...
1
vote
1answer
82 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 ...
0
votes
0answers
47 views

Upper Confidence Bound (UCB) bandit with continuous reward

I would like to know if it is possible to use the UCB bandit in a setting with continuous reward, particularly when the reward is zero-inflated. For instance, if I want to look at revenue or margin, ...
0
votes
1answer
89 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 ...
2
votes
1answer
307 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
46 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
0answers
25 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!
0
votes
0answers
21 views

From multiple Bayesian BetaBinomial bandits models, to logistic regression

Suppose I have a single categorical predictor $X_1$ with K>2 levels, and a binary outcome Y. We have two objectives, in order of priority: Identify if there is level $k$ in $X_1$ that significantly ...
0
votes
0answers
23 views

Batch computation vs online computation

In short, could you explain in which situations online computation is better than batch computation? (I am currently reading a paper (https://arxiv.org/abs/1003.0120) about offline policy evaluation ...
2
votes
1answer
103 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
0answers
13 views

The domain of a policy in a contextual bandit problem

To my understanding, in a contextual bandit problem, each policy is a function from the set of contexts and historical information which consists of triples $(x_t, a_t, r_{a_t})$ where $x_t, a_t, r_{...
0
votes
0answers
72 views

epsilon-greedy strategy for a bandit algorithm - choice of the best epsilon

I'm trying to test a usual $\varepsilon$-greedy strategy for a multi-armed bandit (I'm trying to learn the best bid in a second-price auction). My rewards are $$ r_t = v - y_t, \ {\text if} \ \ ...
0
votes
0answers
24 views

(contextual bandit problem) What does 'identical draw' mean here?

I am currently reading a paper (Learning from Logged Implicit Exploration Data) whose link is below. https://arxiv.org/pdf/1003.0120.pdf The paper supposes we have a set of possibly deterministic ...
0
votes
1answer
61 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
59 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
57 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
0answers
96 views

Proof of Bandit Gradient Algorithm in Suttons Book

I am trying to understand a step in the proof of the "Bandit Gradient Algorithm As Stochastic Gradient Ascent" in Suttons Book (http://incompleteideas.net/book/RLbook2018.pdf) at page 39. Starting ...
0
votes
0answers
17 views

Bandit Problem where only the sum of the rewards is known

Say you have a bandit problem where the only feedback is a) the number of times you pulled arm A b) the number of times you pulled arm B c) the sum total reward associated with A and B on a daily ...
0
votes
0answers
73 views

Multi-armed bandit where you must pull N pulls in T timesteps

Multi-armed bandit where you must pull N pulls in T timesteps Consider the beta-Bernoulli multi-armed bandit, with the following wrinkle: We have a total of $T$ time steps. We must pull $N$ pulls ...
0
votes
1answer
169 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
20 views

MAB UCB1 for variable arms

The Multi Armed Bandits UCB1 algorithm assumes a fixed set of arms each round. How can you adapt this to a setting where new arms can be added in any given round?
0
votes
0answers
27 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
614 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
35 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 ...
1
vote
0answers
35 views

Can statistical inference be performed in a multi-armed bandit scenario?

Statistical inference is the process of using data analysis to deduce properties of an underlying probability distribution. Multi-armed bandit is a technique to try different options and sample more ...
0
votes
1answer
33 views

Multi-armed Bandit :a lower bound for the expected sample size from an inferior population

I am reading Asymptotically efficient adaptive allocation rules to study the multi-armed bandit problem, and have a question. The question is about the proof of Theorem 2. THEOREM 2. Assume that $...
1
vote
0answers
62 views

A multi-armed bandit problem in clinical trial

Suppose that we have two drugs A and B with levels $i=1,\ldots,I$ and $j = 1, \ldots, J$, respectively. These two different drugs are given to patients in a clinical trial. $p_{ij}$ is the prior dose ...
1
vote
1answer
174 views

Offline evaluation of Counter factual data for Recommendation

I am building new model and facing at offline evaluation tasks. My goal is to predict higher CTR(=click/impression) advertisement, and improve sales.(sales would improve if user watch more ...
1
vote
0answers
65 views

Is LinUCB Hannan consistent?

I'm going through the textbook Bandit Algorithms, by Lattimore and Szepesvari (http://downloads.tor-lattimore.com/banditbook/book.pdf). It describes regret bounds for the LinUCB algorithm of the form:...
2
votes
0answers
26 views

Why psuedo regret and not regret is used in adversarial bandits?

In adversarial settings, psuedo regret and not the actual regret is used. The explanation I have been given is that with actual regret the problem is no longer learnable (that is adversary can ...
2
votes
1answer
232 views

Are there frequentist approaches to Thompson Sampling?

What is the theoretical reason why Thompson Sampling needs to involve posterior distributions? Why can we not sample over predictive distributions? (or is the issue that predictive frequentist ...
2
votes
1answer
297 views

Multi armed bandit algorithms failing with un-scaled rewards

I am experimenting with the multi-armed bandit algorithms (namely: epsilon greedy, decaying epsilon greedy, optimistic initial value, upper confidence interval, and Thompson sampling). My reward is ...
1
vote
0answers
54 views

Training a neural network with partial labeling

I want to train a neural network that is part of a multi-armed bandit problem. For each data sample, I have some features representing the context of the sample and there are x neurons in the output ...
3
votes
1answer
63 views

Minor confusion over Thompson sampling

On a paper concerning Thompson sampling (TS) I found a quote: In order to exploit the estimated uncertainties, TS dedicates a higher chance to explore an action if its uncertainty increases. ...
2
votes
2answers
958 views

Multi-armed bandit vs AB testing

I'm trying to understand the difference between AB Testing and Multi armed bandit and when we should use one of the other. It seems to me that Multi-armed bandit algorithms are statistically valid and ...
0
votes
1answer
219 views

Stochastic vs Adversarial Multi-Armed Bandit Problems

I know that the multi-armed bandit can be formalised in multiple ways - two of them being the stochastic and adversarial ways. I am familiar with the fact that adversarial way is a game theoretic ...