Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [multiarmed-bandit]

The tag has no usage guidance.

0
votes
0answers
40 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
43 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
18 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
15 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
70 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
54 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
35 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
20 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
43 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
30 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
102 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
59 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
39 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
35 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
80 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
242 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
229 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
251 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
188 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
107 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
77 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
100 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 ...
0
votes
0answers
13 views

Error of solution ranking

I am exploring subset selection of multi-armed bandits and I am curious about an error measure of a selection. So in the scenario of a multi-armed bandit, a set of arms are present and we aim to ...
1
vote
1answer
107 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
180 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
53 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
341 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
129 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
154 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
103 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
289 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
58 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
159 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
114 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
160 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
964 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, ...
6
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
409 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 ...
4
votes
2answers
216 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 ...
1
vote
1answer
40 views

Posterior sampling for bandit

I am looking at this paper on posterior sampling. The algorithm is on page 8 (image below): Let’s say I have 3 arms and on line 22 arm 3 is the best followed by arm 2 then arm Line 24 calculates the ...
0
votes
1answer
925 views

How to understand k-armed bandit example from Sutton's RL book chapter 2?

I have a trivial problem but I do not understand fully the k-armed bandit theorem from chapter 2. My question is based on Sutton's "Reinforcement Learning: An introduction, second edition". The ...
4
votes
2answers
64 views

Sampling procedure to find distribution of maximal mean (pure exploration no exploitation)

Given n distributions with unknown means, what finite sampling procedure could maximize the probability of finding the distribution with the highest mean? More elaborately: I have n sacks of coins. ...
1
vote
0answers
56 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 ...
3
votes
2answers
948 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 ...
1
vote
0answers
46 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 ...