Answers.Body: <p>To my understanding, the objective of a multi-arm bandit is for the agent to estimate rewards for each arm and then exploit the arm with the best reward.  An agent whose reward <span class="math-container">$R$</span> is equal to the work <span class="math-container">$f_{i,t}(x_{i,t})$</span> would simply exploit the task which did the most work in a time period.  The only way I can conceive of shoehorning this into a MAB is the reward scales with how close to <span class="math-container">$v_i$</span> the total work <span class="math-container">$w_i=\sum_t{f_{i,t}(x_{i,t})}$</span> is getting.  For example <span class="math-container">$R = f_{i,t}(x_{i,t})\frac{v_i - w_i}{v_i}$</span>.</p>
  <p>But I'd also challenge the notion that you do not have state transitions.  A state could be the amount of work performed in the episode for each task.  For example if <span class="math-container">$i = 3$</span>, the starting state is {0, 0, 0} the agent pulls the 2nd lever and 5 work is done.  The new state is {0, 5, 0}.  One might even include <span class="math-container">$T-t$</span> to signal to the agent how many steps it has left in the episode.  In this case the agent could have a clue how close to <span class="math-container">$v_i$</span> it is and if it should start pulling other levers.  This is especially important if one wanted to punish the agent for being severely under <span class="math-container">$v_i$</span> at the end of the episode.  If the work is a real number (as opposed to integer) then there are infinite states but there are ways around this.</p>
  <p>To answer the title question:<br />
  No it is not a problem for a MAB to be episodic.  It might be considered strange because in a classical MAB the reward of an arm is a distribution/function which has no state or relation to time.  But having a finite <span class="math-container">$T$</span> is one way to make the value estimation of a given arm converge.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-23T21:44:43.353Z
Answers.LastActivityDate: 2024-03-23T22:08:58.817Z
Answers.LastEditDate: 2024-03-23T22:08:58.817Z
Answers.UserDisplayName: foreverska
Body: <p>I have this scheduling problem. There are <span class="math-container">$n$</span> jobs, one machine and <span class="math-container">$T$</span> time slots. To be satisfied, each job <span class="math-container">$i=1,\ldots,n$</span> must receive at least the quantity <span class="math-container">$v_i$</span> from the machine. The machine can allocate <span class="math-container">$x_{i,t}\in[0,1]$</span> resources for job <span class="math-container">$i$</span> at each time slot <span class="math-container">$t=1,\ldots,T$</span>. The allocation of <span class="math-container">$x_{i,t}$</span> can produce a quantity <span class="math-container">$f_{i,t}(x_{i,t})\leq v_i$</span> for job <span class="math-container">$i$</span> at time slot <span class="math-container">$t$</span>, where <span class="math-container">$f_{i,t}(\cdot)$</span> is an unknown black-box function that is non-linear and non-convex.</p>
  <p>We have to make sure that each job <span class="math-container">$i=1,\ldots,n$</span> must receive at least the quantity <span class="math-container">$v_i$</span> from the machine, i.e., <span class="math-container">$\sum_{t=1}^T f_{i,t}(x_{i,t})\geq v_{i},\forall i=1,\ldots,n$</span>.</p>
  <p>Can this problem be modelled as multi-armed bandit? I thought that MAB cannot be applied because we have <span class="math-container">$T$</span> time-slots. My issue is that if I use MAB then at each slot the agent will select an action, until <span class="math-container">$T$</span>, then it has to reset again and then start again. Is this an issue?</p>
  <p>On the other side, if I want to apply RL, I have the issue that we don't have state transitions.</p>
  <p>Do you have an idea on how to apply MAB to this problem?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-03-23T15:28:21.587Z
Comments.Text: this seems to be a 'matchmaking on bipartate graph' problem? if so, there is a  quick graph algorithm that solves it: https://www.geeksforgeeks.org/maximum-bipartite-matching/
Comments.UserDisplayName: James
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-03-23T15:49:22.777Z
Comments.Text: How to apply maximum bipartite matching when the function $f_{i,t}$ is not known and you can only evaluate it to get the value at each slot.
Comments.UserDisplayName: zdm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-03-23T16:02:16.050Z
Comments.Text: I gather that there are n jobs that must be completed., but I'm not sure beyond this concretely what is v, what is x, and what is f? Could you maybe provide a plausible scenario (for instance in a factory) what would v, x, and f be?
Comments.UserDisplayName: James
Tags: <reinforcement-learning><multi-armed-bandits>
Title: Can we use MAB in problems that reset after some time?
UserDisplayName: zdm
ThreadText: # Can we use MAB in problems that reset after some time?
  
  (Asked by: username_0 on 2024-03-23)
  
  I have this scheduling problem. There are $n$ jobs, one machine and $T$ time slots. To be satisfied, each job $i=1,\ldots,n$ must receive at least the quantity $v\_i$ from the machine. The machine can allocate $x\_{i,t}\in[0,1]$ resources for job $i$ at each time slot $t=1,\ldots,T$. The allocation of $x\_{i,t}$ can produce a quantity $f\_{i,t}(x\_{i,t})\leq v\_i$ for job $i$ at time slot $t$, where $f\_{i,t}(\cdot)$ is an unknown black-box function that is non-linear and non-convex.
  
  We have to make sure that each job $i=1,\ldots,n$ must receive at least the quantity $v\_i$ from the machine, i.e., $\sum\_{t=1}^T f\_{i,t}(x\_{i,t})\geq v\_{i},\forall i=1,\ldots,n$.
  
  Can this problem be modelled as multi-armed bandit? I thought that MAB cannot be applied because we have $T$ time-slots. My issue is that if I use MAB then at each slot the agent will select an action, until $T$, then it has to reset again and then start again. Is this an issue?
  
  On the other side, if I want to apply RL, I have the issue that we don't have state transitions.
  
  Do you have an idea on how to apply MAB to this problem?
  
  **Tags:** reinforcement-learning, multi-armed-bandits
  
  > **Comments:**
  > **username_1**: this seems to be a 'matchmaking on bipartate graph' problem? if so, there is a  quick graph algorithm that solves it: https://www.geeksforgeeks.org/maximum-bipartite-matching/  
  > **username_0**: How to apply maximum bipartite matching when the function $f_{i,t}$ is not known and you can only evaluate it to get the value at each slot.  
  > **username_1**: I gather that there are n jobs that must be completed., but I'm not sure beyond this concretely what is v, what is x, and what is f? Could you maybe provide a plausible scenario (for instance in a factory) what would v, x, and f be?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2024-03-23. Score: 0
  
  To my understanding, the objective of a multi-arm bandit is for the agent to estimate rewards for each arm and then exploit the arm with the best reward. An agent whose reward $R$ is equal to the work $f\_{i,t}(x\_{i,t})$ would simply exploit the task which did the most work in a time period. The only way I can conceive of shoehorning this into a MAB is the reward scales with how close to $v\_i$ the total work $w\_i=\sum\_t{f\_{i,t}(x\_{i,t})}$ is getting. For example $R = f\_{i,t}(x\_{i,t})\frac{v\_i - w\_i}{v\_i}$.
  
  But I'd also challenge the notion that you do not have state transitions. A state could be the amount of work performed in the episode for each task. For example if $i = 3$, the starting state is {0, 0, 0} the agent pulls the 2nd lever and 5 work is done. The new state is {0, 5, 0}. One might even include $T-t$ to signal to the agent how many steps it has left in the episode. In this case the agent could have a clue how close to $v\_i$ it is and if it should start pulling other levers. This is especially important if one wanted to punish the agent for being severely under $v\_i$ at the end of the episode. If the work is a real number (as opposed to integer) then there are infinite states but there are ways around this.
  
  To answer the title question:  
  No it is not a problem for a MAB to be episodic. It might be considered strange because in a classical MAB the reward of an arm is a distribution/function which has no state or relation to time. But having a finite $T$ is one way to make the value estimation of a given arm converge.
  
  
  ---
  
  