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
0answers
12 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 ...
1
vote
0answers
9 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
8 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
11 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
18 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
30 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
22 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
0answers
38 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
33 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
13 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
42 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
34 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
17 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
44 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
21 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
20 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
23 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
22 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
34 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
61 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
60 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
37 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
18 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 ...
1
vote
1answer
136 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
107 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
42 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
25 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
49 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
41 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
343 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
96 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
46 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
40 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
97 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
331 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
313 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
123 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
2k 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
124 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
163 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
122 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
236 views

RL-gradient bandit algorithm: What's the intuition behind $\mathbb 1_{|A=a}-\pi(A)$?

I'm reading the online draft of "reinforcement learning: an introduction". At section 2.8(Page 59), it introduces gradient bandit algorithm and defines the preference update rule as below (I rewrite ...
1
vote
1answer
56 views

Does there exist a single metric that can compare various Multi-arm Bandit scenarios apples to apples?

I am currently trying to compare how different formulations of a Multi-arm Bandit problem performs across various factors like the variance of the reward distributions of each arm, to the $\epsilon$ ...
0
votes
1answer
520 views

In a multi-arm bandit problem, how does one calculate the cumulative regret in real life?

I was recently looking at some information on Multi-arm Bandits, and they have the notion of cumulative regret. It is defined as the following: Consider $K$ arms, each having a normal distribution ...
2
votes
1answer
192 views

For a Multi-arm Bandits set-up, does the Signal to Noise Ratio have any meaning there?

Suppose that we have a Multi-arm Bandit set-up with $K = 5$ bandits. Each bandit has a reward distribution of: $$ X_i \sim Bern(p_i), \ \ \ i \in \{1, \ldots, 5\} $$ In literature about MABs, ...
2
votes
1answer
177 views

Analysing Regret for Multi Armed Bandits

I am referring to the paper [2012] [Regret Analysis of Stochastic and NonStochastic MAB]1 to understand regret analysis of stochastic multi-armed bandits. In the paper, in Section 2.2, it says the ...