# Can we use MAB in problems that reset after some time?

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?

• this seems to be a 'matchmaking on bipartate graph' problem? if so, there is a quick graph algorithm that solves it: geeksforgeeks.org/maximum-bipartite-matching Commented Mar 23 at 15:28
• 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.
– zdm
Commented Mar 23 at 15:49
• 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? Commented Mar 23 at 16:02

## 1 Answer

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.