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
2
votes
2answers
71 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....
1
vote
0answers
30 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,...
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, ...
2
votes
1answer
39 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
1answer
40 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 ...
1
vote
1answer
52 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
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
1answer
33 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
1answer
29 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
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 ...
7
votes
3answers
476 views

Multi-armed bandit algorithms vs Uplift modeling

Multi-Armed Bandit: http://en.wikipedia.org/wiki/Multi-armed_bandit Uplift Modeling: http://en.wikipedia.org/wiki/Uplift_modelling How are these two approaches different? How are they similar? Is ...
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 ...
3
votes
2answers
415 views

Exploiting features in a multiarmed bandit scenario

I am facing a challenging problem: Say I have shirts of three different colors (same price). And say I am running a strange kind of store in into which people come in one by one, and I can show ...
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 ...
1
vote
1answer
224 views

UCB: where is delta and standard deviation?

One of the most popular multi-armed bandit is the Upper Confidence Bound (UCB) line of algorithms (see references below). My understanding is that we try to find the largest plausible estimate of the ...
0
votes
1answer
39 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 ...
1
vote
1answer
677 views

What are the differences between contextual bandits, actor-citric methods, and continuous reinforcement learning?

Let's imagine we have a blackbox function f(X) -> y which we don't know. X is a vector of 10 continuous variables, which we ...
8
votes
2answers
424 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?
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
1answer
187 views

Time series tracking queue optimization problem

In order to track prices of many different products from different sources, I must optimally schedule a group of trackers dedicated to price collection (ie. collect one price at a time for each ...
2
votes
1answer
144 views

UCB bandit reward bound

The original paper of Auer [1] requires bandit arms to have a reward distribution bounded on [0,1] for the Upper-Confidence-Bound (UCB) theorems to hold. I was wondering how strict this requirement is ...
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, ...
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)^{...
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 ...
3
votes
0answers
89 views

Regret Minimization with Hidden Markov Processes

Consider a hidden Markov process with two states $\{0, 1\}$ represented with $Z_t$. The transition matrix is unknown, although we can assume it's strongly diagonal (i.e. slow-switching). At any time, ...
5
votes
2answers
2k views

Can sub-Gaussian distributions have non-zero mean?

A random variable $X$ is sub-Gaussian if there exists a $b>0$ such that for all $t \in \mathbb{R}$ we have $$\mathbb{E}(\exp(tX)) \leq \exp(b^2t^2/2).$$ According to some sources online such as ...
2
votes
1answer
333 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 ...
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
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 ...
2
votes
1answer
113 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
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
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 ...
1
vote
1answer
70 views

Two armed bandit with a known expectation

Assume a two armed case with bernoulli rewards. We know that UCB1 gives a pretty tight bound for multiarmed bandit cases. What if we know the mean of one arm, how can we obtain a better strategy/...
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
1answer
90 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
185 views

Multi-armed UCB parameter: what is $B$?

UCB uses a padding function such as $$c_t(i)=B\sqrt{\xi \log(t) / N_t(i)},$$ where $B$ is an upper-bound on the reward. This description comes from reference 2 (also see reference 3). But I have seen ...
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 ...
4
votes
1answer
985 views

Gaussian Multi-Armed Bandits and the UCB Algorithm

I've implemented in MATLAB the UCB algorithm for gaussian bandits with zero mean and unit variance (these means were themselves sampled from a gaussian prior of zero mean and unit variance). Now I ...
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 ...
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
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
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
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 ...
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 ...
4
votes
2answers
311 views

Why UCB algorithm (of multi armed bandit) gives i.i.d. reward sequence?

I am reading the proofs of regrets bounds of UCB algorithms, and find the following thing quite confusing. Suppose $T_i(t)$ is the number of times pulling arm $i$, and $I_i(t)$ is set of stages ...
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 ...