A Problem-Adaptive Algorithm for Resource Allocation

02/12/2019
by   Xavier Fontaine, et al.
0

We consider a sequential stochastic resource allocation problem under the gradient feedback, where the reward of each resource is concave. We construct a generic algorithm that is adaptive to the complexity of the problem, which is measured using the exponent in Łojasiewicz inequality. Our algorithm interpolates between the non-strongly concave and the strongly-concave rates without depending on the strong-concavity parameter and recover the fast rate of classical multi-armed bandit (corresponding roughly to linear reward functions).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset