Stack Exchange Network

Stack Exchange network consists of 174 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
10 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:...
0
votes
0answers
19 views
2
votes
0answers
11 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
39 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
25 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
29 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
16 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
30 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
26 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
44 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
39 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
34 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
31 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
21 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
67 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
200 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
143 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
199 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
135 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
83 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
1k 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
31 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
65 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
64 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
95 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
145 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
51 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
232 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 ...
0
votes
0answers
25 views

Calculating p-values in a multi-armed bandit experiment

Suppose I run a multi-armed bandit experiment, where the probability of all treatments are initially equal, though subsequently treatments that appear to be more successful are more likely to be ...
2
votes
1answer
91 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
140 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 ...
0
votes
0answers
12 views

MABs with relative reward

Is there some standard multi-armed bandit problem where in each round you choose an ordered pair of arms $i, j$ and your reward is the difference between the first and the second lever, $R_i-R_j$? If ...
1
vote
1answer
92 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
216 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
54 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
134 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
100 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
134 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
890 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 ...
1
vote
1answer
799 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
3k 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
340 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
181 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
39 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
816 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
702 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 ...