Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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
0
votes
1answer
14 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 ...
1
vote
1answer
24 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
23 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
16 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
16 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
14 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
42 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
9 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
18 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
20 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
33 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
27 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
50 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
55 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
14 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
53 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
58 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
15 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
22 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
211 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. ...
0
votes
0answers
23 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 ...
0
votes
0answers
40 views

Optimal $\gamma$ parameter for the Exp3 algorithm

What is the optimal $\gamma \in (0,1]$ parameter of the Exp3 algorithm for the multi-armed bandit problem, given a fixed number of arms $K$? In my experiments, there seems to be an optimal value but I ...
1
vote
0answers
26 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
24 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
35 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 ...
0
votes
0answers
70 views

Why is the objective of Multi-Armed Bandits (MAB) not the same as the one for Reinforcement Learning (RL)?

I was learning about Multi-Armed Bandits (MAB) and came across the so called regret: $$ R_T(\pi) = \max_{i \in [n]} G_T(i) - G_T(\pi) = \max_{i \in [n] } \sum^T_{t=1} r_{i,t} - \sum^T_{t=1} r_{\pi(t),...
0
votes
1answer
80 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 ...
0
votes
0answers
47 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
21 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
180 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
137 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
45 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 ...
0
votes
0answers
30 views

Contextual Bandit algorithm with agents and arms correlated?

Hi there I am a beginner of multi-arm bandit, I have a similarity measurement problem that I think could be solved with the help of contextual bandit problem, though I am not sure and have few ...
3
votes
1answer
53 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. ...
0
votes
0answers
44 views

Multi-objective multi-armed bandits with binary and continuous rewards

I am dealing with a multi-objective multi-armed bandits problem in which the reward vector is formed by a binary component and a continuous component. I've seen that an approach is to use a ...
0
votes
2answers
499 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
112 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 ...
3
votes
1answer
54 views

Calculating payout of strategy for two one-armed bandits

I am trying to calculate the expected payout of the following strategy: You have two one-armed bandits: one pays out \$$1$ with probability $0.4$, the other pays out \$$1$ with probability $0.5$, you ...
0
votes
1answer
41 views

Why rewards are not relative in UCB?

Consider two 2-arms bandits: average reward first arm is 2 euro, second arm 4 euro average reward first arm is 200 cents, second arm 400 cents From my perspective, the bandits are exactly the same. ...
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
103 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 ...
4
votes
1answer
395 views

How to test if bandit algorithm is converging?

I have coded up the a multi-armed bandit algorithm based on algorithm 1 in the original LinUCB algorithm paper, but I am having trouble determining if it is working properly. My test setup is the ...
0
votes
1answer
18 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
1answer
354 views

Adapting UCB1 algorithm for contextual bandits

I am using the UCB1 algorithm to solve the multi-armed bandit problem and I would like to adapt it to handle some context vector that would influence the UCB algorithm that makes recommendations. Is ...
3
votes
0answers
131 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 \...
-1
votes
1answer
3k views

what is epsilon/k in epsilon greedy algorithm [closed]

As it was told it would choose the arm having highest emperical mean with probability 1-epsilon how did epsilon/k add to it (and also epsilon/k for random probability selection)in the equation written ...
-1
votes
1answer
32 views

Algorithms for mulit armed bandit problems

Algorithms for multi armed bandit problems can some one explain what are the x and y axis for the graphs in the research paper"algorithms for multi armed bandits" in page no: 11
1
vote
1answer
152 views

Q-Learning: state independent of agent's action [closed]

Could state be independent of the action chosen by agent? We would have a situation in which agent learns only which actions are the best in specific states without having any impact on those states (...
0
votes
1answer
192 views

Regret formulation in stochastic multi-armed bandit problem

In this paper, there are two formulations of regret at time $n$: $R_n=n\mu^*-\sum_{t=1}^{n}E[\mu_{I_{t}}]$ $R_n=\sum_{i=1}^{K}\Delta_iE[T_i(n+1)]$ Where $\mu_i$ is an expected value of some ...
1
vote
1answer
135 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 ...