非確率的な multi-armed bandit 問題における分散投資の効果について  [in Japanese] On effect of balancing investment in nonstochastic multi-armed bandit problems  [in Japanese]

Search this Article

Author(s)

Abstract

multi-armed bandit問題とは、異なるK個のスロットマシンから1台のマシンを選択するという試行を繰り返し行う状況において、総合利得を最大化するようにマシンを選択する問題である。ほとんどの従来手法では各スロットマシンから得られる報酬は確率的に定まるという仮定のもとに分析が行われてきた。一方、Auerらは報酬に確率的な仮定をおかない一般的な場合を考え、損失の上界が理論的に保証されたアルゴリズムを示した。本報告では、この問題を一度に複数のスロットマシンを選択できるように拡張し、分散投資効果について理論的に分析する。

The multiarmed bandit problem is a problem in which a gambler chooses one arm of K nonidentical slot machines to play in a sequence of trials so as to maximize his reward. Past solutions for the bandit problem have almost always relied on assumptions about the statistics of the slot machines. On the other hand, Auer et al. made no statistical assumption whatsoever about the nature of the process generating the payoffs of the slot machine. They gave solutions to the bandit ploblem in which an adversary has complate control over the payoffs. In this paper, we extend this problem to the problem of choosing more than one slot machine at a time and theoretically analyze it.

Journal

  • IEICE technical report

    IEICE technical report 108(363), 213-218, 2008-12-11

    The Institute of Electronics, Information and Communication Engineers

References:  3

Codes

  • NII Article ID (NAID)
    110007123759
  • NII NACSIS-CAT ID (NCID)
    AN10541106
  • Text Lang
    JPN
  • Article Type
    ART
  • ISSN
    09135685
  • NDL Article ID
    9764725
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    CJP  NDL  NII-ELS 
Page Top