Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards - Mathematics > Optimization and ControlReportar como inadecuado




Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards - Mathematics > Optimization and Control - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In the classic multi-armed bandits problem, the goal is to have a policy fordynamically operating arms that each yield stochastic rewards with unknownmeans. The key metric of interest is regret, defined as the gap between theexpected total reward accumulated by an omniscient player that knows the rewardmeans for each arm, and the expected total reward accumulated by the givenpolicy. The policies presented in prior work have storage, computation andregret all growing linearly with the number of arms, which is not scalable whenthe number of arms is large. We consider in this work a broad class ofmulti-armed bandits with dependent arms that yield rewards as a linearcombination of a set of unknown parameters. For this general framework, wepresent efficient policies that are shown to achieve regret that growslogarithmically with time, and polynomially in the number of unknown parameterseven though the number of dependent arms may grow exponentially. Furthermore,these policies only require storage that grows linearly in the number ofunknown parameters. We show that this generalization is broadly applicable anduseful for many interesting tasks in networks that can be formulated astractable combinatorial optimization problems with linear objective functions,such as maximum weight matching, shortest path, and minimum spanning treecomputations.



Autor: Yi Gai, Bhaskar Krishnamachari, Rahul Jain

Fuente: https://arxiv.org/







Documentos relacionados