Участник:Dyzzet/Многорукий бандит
Материал из Википедии — свободной encyclopedia
В теории вероятностей многорукий бандит (англ. K-[1] or N-armed bandit problem[2]) — это задача, в которой фиксированное конечное множество ресурсов должно быть распределено между соревнующимися (альтернативными) вариантами таким способом, чтобы получить максимальную выгоду, причём свойства каждого из вариантов в момент распределения ресурсов известны лишь частично, а более полное их понимание может наступить через некоторое время или после распределения ресурса определённому варианту[3][4]. Это классическая задача обучения с подкреплением, которая ищет компромисс между исследованием и применением (англ. exploration–exploitation tradeoff dilemma), иными словами — между тем, продолжать исследование или применять уже имеющиеся знания). Название происходит от воображаемого азартного игрока, сидящего у игровых автоматов («однорукие бандиты»), которому нужно решить, на каких автоматах лучше играть, сколько раз играть на каждом из них и в каком порядке, продолжать ли играть на текущем автомате или переходить к следующему[5]. Задача о многоруких бандитах также является разновидностью широкой категории задач вероятностного планирования.
In the problem, each machine provides a random reward from a probability distribution specific to that machine. The objective of the gambler is to maximize the sum of rewards earned through a sequence of lever pulls.[3][4] The crucial tradeoff the gambler faces at each trial is between "exploitation" of the machine that has the highest expected payoff and "exploration" to get more information about the expected payoffs of the other machines. The trade-off between exploration and exploitation is also faced in machine learning. In practice, multi-armed bandits have been used to model problems such as managing research projects in a large organization like a science foundation or a pharmaceutical company.[3][4] In early versions of the problem, the gambler begins with no initial knowledge about the machines.
Herbert Robbins in 1952, realizing the importance of the problem, constructed convergent population selection strategies in "some aspects of the sequential design of experiments".[6] A theorem, the Gittins index, first published by John C. Gittins, gives an optimal policy for maximizing the expected discounted reward.[7]