Deterministic Losses における同時最適的な静的・動的損失の達成：バンディット問題

arXiv:2602.07418v1 発表タイプ：新規 要約：敵対的マルチアームバンディットでは、2 つのパフォーマンス指標が一般的に使用されています：ベスト固定アームと比較する静的損失（static regret）と、ベストアームの順列と比較する動的損失（dynamic regret）。個々の指標に対して最適なアルゴリズムは既知ですが、両方を同時に最適 bound で達成するアルゴリズムは既知ではありません。Marinov と Zimmert [2021] は、適応的敵対者に対してこのような同時最適性は不可能であることを初めて示しました。当研究では、損失が確定値である場合、無知覚（oblivious）敵対者に対してその可能性を実証する最初のステップを取ります。まず、Marinov と Zimmert [2021] の不可能性結果を確定値損失の場合に拡張します。次に、無知覚敵対者に対して同時最適的な静的・動的損失を達成するアルゴリズムを提案します。これらは、複数の損失ベンチマークを同時に考慮する場合、適応的敵対者と無知覚敵対者の間に根本的な区別が存在することを示唆します。また、異なる数のスイッチを有する切り替えるベンチマークに対して同時最適な損失を達成するという長期にわたる未解決問題に対する新たな洞察を提供します。 我々のアルゴリズムは、動的損失の制御に伴う探査オーバーヘッドを補うために負の静的損失（negative static regret）を利用し、Blackwell の到達可能性（approachability）を併用して両方の損失を統制します。これは、バンディットに対する新しいモデル選択手順を提供し、独立した興味を惹き起こす可能性があります。

arXiv:2602.07418v1 Announce Type: new Abstract: In adversarial multi-armed bandits, two performance measures are commonly used: static regret, which compares the learner to the best fixed arm, and dynamic regret, which compares it to the best sequence of arms. While optimal algorithms are known for each measure individually, there is no known algorithm achieving optimal bounds for both simultaneously. Marinov and Zimmert [2021] first showed that such simultaneous optimality is impossible against an adaptive adversary. Our work takes a first step to demonstrate its possibility against an oblivious adversary when losses are deterministic. First, we extend the impossibility result of Marinov and Zimmert [2021] to the case of deterministic losses. Then, we present an algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary. Together, they reveal a fundamental separation between adaptive and oblivious adversaries when multiple regret benchmarks are considered simultaneously. It also provides new insight into the long open problem of simultaneously achieving optimal regret against switching benchmarks of different numbers of switches. Our algorithm uses negative static regret to compensate for the exploration overhead incurred when controlling dynamic regret, and leverages Blackwell approachability to jointly control both regrets. This yields a new model selection procedure for bandits that may be of independent interest.