Abstract <p> The multi-armed bandit problem is considered in application to the batch processing of big data, given more than two alternative processing methods with different, a priori unknown, efficiencies. During processing, it is required to identify the most effective method and to ensure its preferential use. The control is performed on the basis of cumulative rewards in batches, which have approximately Gaussian distribution by virtue of the central limit theorem. An important feature of batch processing is that it almost does not lead to an increase in the maximum loss of the total expected reward, i.e., to an increase in the minimax risk, if the numbers of processed data items and the number of batches the data are divided into are sufficiently large. This means that a Gaussian multi-armed bandit provides a universal approach to the optimal control of big data processing if one-step rewards satisfy the central limit theorem. According to this approach, the minimax strategy and risk can be found using the fundamental theorem of game theory as the Bayesian strategy and risk calculated with respect to the worst-case prior distribution, at which the Bayesian risk is maximal. For this purpose, a characterization of the worst-case prior distribution is given and recursive equations in the usual and invariant forms with a control horizon equal to one are obtained. In the limiting case when the number of processed batches tends to infinity, a second-order partial differential equation is obtained. A numerical example of computation of the minimax risk and strategy for a three-armed bandit is given. </p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Minimax Approach to the Gaussian Multi-Armed Bandit

  • A. V. Kolnogorov

摘要

Abstract

The multi-armed bandit problem is considered in application to the batch processing of big data, given more than two alternative processing methods with different, a priori unknown, efficiencies. During processing, it is required to identify the most effective method and to ensure its preferential use. The control is performed on the basis of cumulative rewards in batches, which have approximately Gaussian distribution by virtue of the central limit theorem. An important feature of batch processing is that it almost does not lead to an increase in the maximum loss of the total expected reward, i.e., to an increase in the minimax risk, if the numbers of processed data items and the number of batches the data are divided into are sufficiently large. This means that a Gaussian multi-armed bandit provides a universal approach to the optimal control of big data processing if one-step rewards satisfy the central limit theorem. According to this approach, the minimax strategy and risk can be found using the fundamental theorem of game theory as the Bayesian strategy and risk calculated with respect to the worst-case prior distribution, at which the Bayesian risk is maximal. For this purpose, a characterization of the worst-case prior distribution is given and recursive equations in the usual and invariant forms with a control horizon equal to one are obtained. In the limiting case when the number of processed batches tends to infinity, a second-order partial differential equation is obtained. A numerical example of computation of the minimax risk and strategy for a three-armed bandit is given.