同値クエリから学ぶことを再考する

要旨: 生成モデルやレコメンデーションシステムのような現代の機械学習システムは、多くの場合、導入、ユーザとの相互作用、そして定期的なモデル更新というサイクルを通じて発展します。これは、損失や後悔の最小化を、固定された一連の予測タスクにわたって行うことに焦点を当てた標準的な教師あり学習の枠組みとは異なります。この状況に動機づけられ、Angluin (1988) によって導入された、同値クエリから学習するという古典的モデルを再検討します。このモデルでは、学習者が仮説を繰り返し提案し、導入された仮説が不十分な場合には反例を受け取ります。しかし、反例生成が完全に敵対的であると、モデルは過度に悲観的になり得ます。さらに、従来の研究の多くは
\emph{完全情報} の設定、つまり学習者が反例の正しいラベルも観測するという仮定を置いていますが、この仮定は必ずしも自然とは限りません。

これらの問題に対処するため、環境を、敵対性がより弱い広いクラスの反例生成器に制限します。これを
\emph{対称} と呼びます。非形式的に言えば、そのような生成器は、仮説と目標の対称差のみに基づいて反例を選びます。このクラスは、自然なメカニズムを捉えます。たとえばランダムな反例（Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024）や、あらかじめ定めた複雑度指標に従って最も単純な反例を返す生成器です。この枠組みのもとで、完全情報とバンディットフィードバックの両方における同値クエリからの学習を研究します。両設定における学習ラウンド数についてタイトな境界を得るとともに、今後の研究の方向性を示します。解析は、対称な敵対者をゲーム論的に捉える視点と、適応的重み付け手法、そしてミニマックスの議論を組み合わせています。