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.

53 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
241 views

Bandits with mixed reward processes?

I am trying to model a sequential exploration-exploitation problem with learning as a multi-armed bandit, where the reward mixes a Markovian and a stochastic reward. I understand how to model a ...
4
votes
0answers
309 views

Multi armed bandits with known reward estimates

Consider a bandit problem in which you know the set of expected payoffs for pulling various arms, but you do not know which arm maps to which expected payoff. Can you design a regret minimizing ...
4
votes
0answers
327 views

Optimal Stopping for Bernoulli One-Armed Bandit with a Fixed, Known Payout

I'm very new to bandit problems (apologies if I've formatted my question incorrectly), but I have to solve the optimal stopping of what I think is a very simple case. Suppose I have two arms $k = {1, ...
3
votes
1answer
61 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 ...
3
votes
0answers
156 views

Thompson sampling with adaptive kernel density estimation

This is an extension to this question, which is about handling arbitrary (potentially unbounded) reward distributions for the multi-armed bandit problem. Given a sequence of observed rewards $r_t \in \...
3
votes
0answers
91 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, ...
3
votes
2answers
425 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 ...
2
votes
0answers
27 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
253 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 ...
2
votes
1answer
730 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 ...
2
votes
1answer
50 views

Beta Binomial Encryption

For the sake of example, suppose we have a list of advertisements $\{A_i\}_{i=1}^n$, each of which have parameters $I_i$: the number of impressions, and $C_i$ the number of clicks. Then $C_i/I_i$ ...
2
votes
1answer
146 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 ...
2
votes
0answers
67 views

How are these two multi-armed bandit problems similar?

I am reading the multi-armed bandit survey by Bubeck and Bianchi. This question is for the lower bound section (2.3) of the survey. Let us define $kl(p, q) = p \log \frac{p}{q} + (1- p) \log \frac{1-p}...
2
votes
0answers
61 views

Collaborative Maximum Costly Sequential Multi-armed Bandit

My problem is similar to the multi-armed bandit problem in that I need to allocate "pulls" between n options, each giving a stochastic real reward. The pulls for a ...
2
votes
0answers
917 views

How can I (numerically) approximate the quantile in a beta distribution in SQL?

I wrote some code in SAS that among other things, used the BETAINV function (or BETA.INV as it's called in Microsoft Excel) to calculate the quantile in a beta distribution corresponding to a random ...
2
votes
0answers
857 views

How to work with an improper uniform prior in R?

I'm coding some Bayesian bandits algorithms for exponential families and for the case when my rewards are normally distributed, I need to use an improper uniform prior. Is there any way to represent ...
2
votes
0answers
629 views

Thompson sampling with multivariate posterior distribution

I'm implementing Thompson sampling for a multi armed bandit problem (see http://en.wikipedia.org/wiki/Thompson_sampling). The underlying Bayesian model is a Bayesian Linear Regression, which has a ...
1
vote
1answer
31 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?
1
vote
1answer
39 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 ...
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 ...
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
38 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 ...
1
vote
0answers
66 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
0answers
69 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:...
1
vote
0answers
58 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 ...
1
vote
0answers
22 views

Reinforcement learning for segmenting robot's path to reflect the true distances

I've a grid of rectangles acting as blocks. The robot traverses through the inter-spaces between these consecutive blocks. Now I have sensor data streaming in representing Right and left wheel speeds. ...
1
vote
0answers
157 views

Bayesian learning - how to update an inverse gamma distribution

I'm trying to implement a Bayesian Learning/Updating Model (multi-armed bandit) in the following way: I'm conducting a survey where respondents can rate items on a 5-point scale. I have a total set ...
1
vote
0answers
208 views

How to tune parameters in multi-armed bandit problem

Many multi-armed bandit algorithms involve some parameters, such as temperature of Boltzmann exploration, e in e-greedy, and so on. As suggest in the paper Precup 2000 (Algorithms for the multi-...
1
vote
0answers
73 views

Probability of $\text{arg}\max_i \mathbb{E}(X_i)$ with limited samples

We place ourselves in a multi-armed bandit setting. Each arm yields a stochastic reward in $[0,1]$ under an unknown distribution. After several pulls ($n_i$ pulls for arm $i$), we collect a dataset ...
1
vote
0answers
52 views

Duelling Bandits

Let us say that we have some collection of players $P_0..P_{N-1}$ in a zero-sum win/loss game, and the expected win rate of $P_i$ against $P_j$ is given by $w_{ij}$. Define the skill $S_i$ of a player ...
1
vote
1answer
72 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/...
1
vote
0answers
331 views

Why does SGD converge for optimizing an expectation if expected update equals the actual gradient?

When optimizing an expected value, why is it true that stochastic updates will converge as long as the expected value of the update is equal to the corresponding gradient of the expected value? For ...
1
vote
0answers
37 views

Optimal policy for expert selection (1-step bandit problem)

Suppose I have 3 expert who have provided answers to a binary classification problem. The experts have different (stationary) policies giving an (unknown) true $P_e(correct)$, and we also have ...
1
vote
0answers
54 views

Multi-arm bandit with partial observability

I've been trying to find a formulation of the multi-arm bandit problem with partial observibility. The motivation is that it may be hard to identify that one arm is different from another in some ...
0
votes
0answers
8 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 ...
0
votes
0answers
10 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
0answers
28 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
17 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 ...
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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
21 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
67 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 ...
0
votes
0answers
31 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 ...
0
votes
0answers
59 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
50 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!
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
21 views

Statistical methods to measure effectiveness of communication channels

Does anyone know of any techniques to measure the effectiveness of marketing calls/messages/mails basically any sort of communication channel used? In general you can have several statuses for a ...
0
votes
0answers
62 views

Numerical Approximations for optimum epsilon Multi-Armed-Bandit

Aside from raw simulation, are there numerical approximations of cumulative reward curves for epsilon-greedy bandits with bernoulli arms? Specifically, I would like to approximate these reward curves ...
0
votes
0answers
77 views

Are there other terms for “multi-armed bandit experiments”?

In a multi-armed bandit experiment, many treatments (or actions) are compared, and we aim to discover the best treatments in a short time (wikipedia, google analytics) Do other fields (maybe ...