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
5
votes
1answer
83 views
+50

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
10 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 ...
0
votes
0answers
23 views

Deriving Hyperparameter updates in Online Interactive Collaborative Filtering

I've been going through "Online Interactive Collaborative Filtering Using Multi-Armed Bandit with Dependent Arms" by Wang et al. and am unable to understand how the update equations for the ...
4
votes
2answers
43 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 ...
2
votes
1answer
66 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
41 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
30 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
1
vote
1answer
44 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
426 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
41 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
36 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 ...
1
vote
1answer
59 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
1answer
34 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
2answers
72 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
51 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
52 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
91 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
338 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
47 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
30 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
22 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
25 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
114 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
25 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
66 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
64 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
100 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
18 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
177 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
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
623 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
36 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
34 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
64 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
184 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
67 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
237 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
307 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
55 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 ...