Questions tagged [multi-armed-bandits]
For questions related to the multi-armed bandit (MAB) 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.
29
questions with no upvoted or accepted answers
3
votes
0
answers
26
views
Mapping given probabilities to empirical probabilities
Consider following problem statement:
You have given $n$ actions. You can perform any of them. Each action gives you success with some probability. The challenge is to perform given finite number of ...
- 221
2
votes
0
answers
91
views
Is it better to model a Contextual Multi-Armed Bandit problem as an MDP with a non-zero discount factor than treating it as it is?
I'd like to ask if it is, generally, better to model a problem that naturally appears as a Contextual Multi-Armed Bandit like Recommender Systems as a Markov Decision Process with a non-zero discount ...
- 519
2
votes
0
answers
50
views
Multi-armed bandit problem without getting rewards
In a 2-armed-bandit problem, an agent has an opportunity to see n reward for each action. Now the agent should choose actions m times and maximize the expected reward in these m decisions. but it cant ...
- 121
2
votes
0
answers
70
views
Is there a UCB type algorithm for linear stochastic bandit with lasso regression?
Why is there no upper confidence bound algorithm for linear stochastic bandits that uses lasso regression in the case that the regression parameters are sparse in the features?
In particular, I don't ...
- 21
2
votes
0
answers
114
views
Solving multi-armed bandit problems with continuous action space
My problem has a single state and an infinite amount of actions on a certain interval (0,1). After quite some time of googling I found a few paper about an algorithm called zooming algorithm which can ...
- 21
1
vote
2
answers
50
views
References on Theoretical Bandit Problem
I am going to start learning the bandit problem and algorithm, especially how to bound the regret. I found the book ``Bandit Algorithms'' but it is not easy to follow. It is based on advanced ...
- 471
1
vote
0
answers
35
views
Data Imbalance in Contextual Bandit with Thompson Sampling
I'm working with the Online Logistic Regression Algorithm (Algorithm 3) of Chapelle and Li in their paper, "An Empirical Evaluation of Thompson Sampling" (https://papers.nips.cc/paper/2011/...
- 11
1
vote
0
answers
54
views
Policy gradient (or more general, RL algorithms) for the problems where actions does not determine next state (next state is independent to action)
I am pretty new in RL. Could anyone suggest results/paper about whether or not policy gradient (or more general RL algorithms) can be applied to the problems where actions does not determine next ...
- 11
1
vote
1
answer
27
views
If the probabilities with which each task is selected for you do not change over time, why would it appear as a single stationary k-armed bandit task?
Sutton-Barto (Section 2.9-Associative Search (Contextual Bandits), page 41):
As an example, suppose there are several different k-armed bandit tasks, and that on
each step you confront one of these ...
- 179
1
vote
0
answers
50
views
Can vanilla multi armed bandit problems be solved by RL algorithms like A2C and PPO?
Let's say we have N bandit machines with some distributions (assume some are gaussian, some are uniform, some are chi squared). We want to maximize rewards in X amount of time. I am aware that ...
- 159
1
vote
0
answers
79
views
Is there a paper/article on contextual $\epsilon$-greedy algorithm?
I am reading the paper A Contextual-Bandit Approach to Personalized News Article Recommendation, where it refers to $\epsilon$-greedy (disjoint) algorithm. I suspect, that it is just a version of a K-...
- 223
1
vote
0
answers
45
views
Multi-armed Bandit in optimization on graph edges selection
I have the problem, which I described below. I wonder if there exists a class of multi-armed bandit approaches that is related to it.
I am working on computer networking optimization.
In the simplest ...
- 21
1
vote
0
answers
75
views
Which RL algorithm would be suitable for this multi-dimensional and continuous action space?
Is there an RL approach/algorithm that would be suited for the following kind of problem?
There is a continuous action space with an action value $A_{a,t}$ for each action dimension $a$.
The ...
- 11
1
vote
0
answers
144
views
UCB-like algorithms: how do you compute the exploration bonus?
My question concerns Stochastic Combinatorial Multiarmed Bandits. More specifically, the algorithm called CombUCB1 presented in this paper. It is a UCB-like algorithm.
Essentially, in each round of ...
- 11
1
vote
0
answers
82
views
How do I learn the value function for a POMDP with a single-step horizon (bandit)?
Consider a POMDP with a finite number of environment states, $|\mathcal{S}| = N$, but the number of belief states is uncountably infinite. The belief state space is the convex hull of an $N$ simplex. ...
- 61
1
vote
0
answers
41
views
Multi-armed bandits: reducing stochastic multi-armed bandits to bernoulli bandits
Agrawal and Goyal (http://proceedings.mlr.press/v23/agrawal12/agrawal12.pdf page 3) discussed how we can extend Thompson sampling for bernoulli bandits to Thompson sampling for stochastic bandits in ...
- 287
1
vote
0
answers
502
views
Understanding GLIE conditions for epsilon greedy approach
I was going through this course on reinforcement learning (the course has two lecture videos and corresponding slides) and I had a doubt. On slide 18 of this pdf, it states following condition for an ...
- 131
1
vote
0
answers
31
views
Customized food for persons based on their profile using Reinforcement learning
I am newbie to Reinforcement Learning, this is my idea - Agent(food provider) has to select a food based on the environment(based on the user profile). Here the reward will be given to the agent based ...
- 11
1
vote
0
answers
56
views
How do I determine the optimal policy in a bandit problem with missing contexts?
Suppose I learn an optimal policy $\pi(a|c)$ for a contextual multi-armed bandit problem, where the context $c$ is a composite of multiple context variables $c = c_1, c_2, c_3$. For example, the ...
- 11
1
vote
0
answers
33
views
Name of a multiarmed bandit with only some levers available
In order to model a card game, as an exercise, I was thinking of an elementary setting as a multiarmed bandit, each lever being the distribution of expected rewards of a specific card.
But, of course,...
- 51
0
votes
0
answers
19
views
What reinforcement learning algorithm should I use for the following problem?
Environment
I have a static timeseries environment meaning the environment is the same.
This problem is a multi armed bandit problem.
Time
t0
t1
t2
State
s0
s1
s2
Score
10
0.1
0.2
Class
1
0
0
...
- 1
0
votes
0
answers
15
views
Framing a resource allocation problem without sequential action for Reinforcement Learning
I am attempting to get some insight into framing a resource allocation problem using Reinforcement Learning (RL) where there seem to be no sequential actions (I might be incorrect here).
In my ...
- 101
0
votes
0
answers
8
views
References for Stochastic Process for Sequential Decision Making
I am reading papers on Multi-armed bandit problem. In these papers, they use some notations in measure-theory like filtration, adapted filtration, and so on. Also, to prove theorems, many papers ...
- 471
0
votes
0
answers
26
views
UCB algorithm exercise
I am trying to understand the UCB algorithm and I'm trying to understand it using an exercise. Here's the Upper Confidence Bound algorithm explanation:
Now I have the following exercise: Suppose we ...
- 113
0
votes
0
answers
40
views
How to model the probability of click-through in bandit problem?
Consider a bandit problem in which we want to maximize the probability of click-through based on bid values ($b$ is the value of bid and $\Pr(b)$ shows the probability that a customer clicks on a link ...
- 471
0
votes
0
answers
60
views
Will adding new arms after every time step still make the problem a Multi Armed Bandit problem?
In Multi Armed Bandit problem, let's say I have 4 arms- {S1, S2, S3, S4}. Each arm has their own probability distribution of rewards. I play the first arm (S1); I get +2 as reward. I add 2 more arms ...
- 159
0
votes
0
answers
46
views
Is there a variant of Thompson Sampling that works with variable bandits?
Does there exist a variant of TS, such that, while computing the returns of multi-armed bandits, we have the possibility of introducing an extra bandit?
For instance, while we are applying TS to 3 ...
- 460
0
votes
0
answers
73
views
Are Best-Arm Bandits considered to be reinforcement learning?
Multi Armed Bandits (MABs) are a broad field of research pursuing different streams. In addition to the common objective of maximizing the cumulative reward, there are also so-called Best-Arm (...
- 101
0
votes
0
answers
74
views
Which algorithms work in a non-stationary stochastic environment?
Currently, I am reading into the Multi-Armed-Bandit problem and found the special case of non-stationary (environment and its attributes, like the reward distribution, change over time) stochastic ...
