# Incentivized Lipschitz Bandits

## 背景

- 多腕バンディット（MAB）問題は、無限のアームを持つ設定での探索と利用のトレードオフを扱う。

- 従来のモデルとは異なり、意思決定者（プリンシパル）が短期的なエージェントに報酬を与え、貪欲な選択を超えた探索を促す状況を考慮。

## 課題

- インセンティブによる報酬の偏り（リワードドリフト）が発生し、エージェントのフィードバックがバイアスされる。

- 無限のアーム空間を均一に離散化し、探索アルゴリズムを設計する必要がある。

## 手法

- 新しいインセンティブ探索アルゴリズムを提案。

- アーム空間を均一に離散化し、累積的な後悔と総補償を同時にサブリニアに達成。

- 後悔と補償の境界を$\Tilde{O}(T^{d+1/d+2})$として導出（$d$はメトリック空間のカバリング次元）。

- コンテキストバンディットへの一般化も行い、同様の性能保証を達成。

## 結果

- 提案したアルゴリズムは、理論的な結果を数値シミュレーションで検証。

- サブリニアの後悔と補償を実現し、実用的なアプリケーションにおける有効性を示す。

## 限界 / 今後の展望

- 提案手法は特定のメトリック空間に依存しており、他の空間への適用可能性は未検討。

- インセンティブ設計の複雑さや、エージェントの行動モデルの多様性に対する対応が必要。

- 今後の研究では、異なるタイプのエージェントや環境におけるアルゴリズムの適用を探求することが求められる。