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.

0
votes
0answers
7 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
14 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
29 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
16 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
11 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
20 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
21 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
29 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
56 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
53 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
28 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
17 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
109 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 ...
1
vote
1answer
94 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
36 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
22 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 ...
2
votes
1answer
47 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
39 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
214 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
72 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
44 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
37 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
92 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 ...
0
votes
0answers
280 views

Epsilon Greedy Performing better than UCB

I am implementing the bandit problem using various algorithms. The issue that i am facing is that epsilon greedy is performing better than UCB for 5arms and horizon of 2000 for epsilon value of 0.95. ...
3
votes
1answer
280 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
17 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
284 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 ...
0
votes
0answers
236 views

Do Bayesian Optimization GP-UCB algorithm always converged for any continuous function in theory or practice?

Recently,I am studying the paper of Gaussian Process Optimization in the Bandit Setting, Srinivas. In theorem 3, they state: Let $\delta\in(0,1)$. Assume that the true underlying f lies in the RKHS ...
3
votes
0answers
120 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
91 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
137 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
117 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
221 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
55 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
444 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
171 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
169 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 ...
1
vote
1answer
120 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 ...
1
vote
1answer
355 views

EXP4 algorithm for contextual bandits: where do experts come from?

I am working on an implementation of the EXP4 algorithm in the context of a pricing decision (e.g. given a context, the user should be given a price from a few pre-determined options). The EXP4 uses "...
1
vote
1answer
59 views

Is this a contextual bandit problem?

I have an operations research problem that I would like to solve but I am unsure what the correct framework for analyzing it would be. The closest I've come across so far is contextual bandits I ...
0
votes
1answer
201 views

multi armed Bandit Problem

I am studying machine learning, I remember what are distributions, mean, median mode, from my university statistics studies, but the author, says that given five slot machines with these distributions,...
1
vote
0answers
136 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-...
0
votes
1answer
178 views

How to update multiple arms in a multi-armed bandit problem?

I'm relatively new to reinforcement learning and have the following multi-armed bandit problem: Let's assume we have a bandit with $n$ arms. Each arms has a different reward distribution with support ...
3
votes
2answers
1k views

Gradient Bandit Algorithm baseline

I am reading Sutton's latest draft of "Reinforcement learning, an introduction" and I came to the Gradient Bandit Algorithm (page 29). I am having a bit of trouble understanding how the baseline ...
2
votes
1answer
1k views

UCB1 for Multi Armed Bandit is stochastic or deterministic?

I would like to know if UCB1 for multi armed bandit problems is deterministic or stochastic. I understand that the arm chosen depends on the expected reward and the "width" of the upper bound, ...
7
votes
2answers
4k views

Upper Confidence Bound in Machine Learning

I came across the formula for obtaining the upper confidence bounds on the k-armed bandit problem: $$c\sqrt{\frac{\text{ln} N_i}{n_i}}$$ where $n_i$ is the amount of samples we have for this ...
1
vote
1answer
474 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 ...