0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – James
    Commented Mar 23 at 15:28
  • $\begingroup$ 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. $\endgroup$
    – zdm
    Commented Mar 23 at 15:49
  • $\begingroup$ 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? $\endgroup$
    – James
    Commented Mar 23 at 16:02

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .