論文の概要: Strategic Apple Tasting
- arxiv url: http://arxiv.org/abs/2306.06250v1
- Date: Fri, 9 Jun 2023 20:46:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-13 20:11:59.396751
- Title: Strategic Apple Tasting
- Title（参考訳）: 戦略的アップル味覚
- Authors: Keegan Harris, Chara Podimata, Zhiwei Steven Wu
- Abstract要約: ハイテイク領域におけるアルゴリズムによる意思決定は、しばしばアルゴリズムへの入力を戦略的に修正するインセンティブを持つエージェントに決定を割り当てる。
我々は、この設定をリンゴ味のフィードバックによるオンライン学習問題として定式化する。
我々の目標は、プリンシパルのパフォーマンスを後見の最良の固定政策のパフォーマンスと比較する、サブリニアな戦略的後悔を達成することです。
- 参考スコア（独自算出の注目度）: 31.80415035694403
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Algorithmic decision-making in high-stakes domains often involves assigning
decisions to agents with incentives to strategically modify their input to the
algorithm. In addition to dealing with incentives, in many domains of interest
(e.g. lending and hiring) the decision-maker only observes feedback regarding
their policy for rounds in which they assign a positive decision to the agent;
this type of feedback is often referred to as apple tasting (or one-sided)
feedback. We formalize this setting as an online learning problem with
apple-tasting feedback where a principal makes decisions about a sequence of
$T$ agents, each of which is represented by a context that may be strategically
modified. Our goal is to achieve sublinear strategic regret, which compares the
performance of the principal to that of the best fixed policy in hindsight, if
the agents were truthful when revealing their contexts. Our main result is a
learning algorithm which incurs $\tilde{\mathcal{O}}(\sqrt{T})$ strategic
regret when the sequence of agents is chosen stochastically. We also give an
algorithm capable of handling adversarially-chosen agents, albeit at the cost
of $\tilde{\mathcal{O}}(T^{(d+1)/(d+2)})$ strategic regret (where $d$ is the
dimension of the context). Our algorithms can be easily adapted to the setting
where the principal receives bandit feedback -- this setting generalizes both
the linear contextual bandit problem (by considering agents with incentives)
and the strategic classification problem (by allowing for partial feedback).
- Abstract（参考訳）: アルゴリズムによる意思決定は、しばしばアルゴリズムへの入力を戦略的に修正するインセンティブを持つエージェントに決定を割り当てる。
インセンティブを扱うことに加えて、多くの関心領域(例えば貸付や雇用)において、意思決定者は、エージェントに肯定的な決定を割り当てるラウンドに対する政策に関するフィードバックのみを観察する。
私たちは、この設定をapple-tastingフィードバックによるオンライン学習問題として定式化し、プリンシパルが$t$エージェントのシーケンスについて決定を下します。
我々の目標は、もしエージェントが彼らの状況を明らかにする際に真実であるならば、プリンシパルのパフォーマンスを後見の最良の固定政策のパフォーマンスと比較する、サブリニアな戦略的後悔を達成することです。
我々の主な成果は、エージェントの列が確率的に選択されたときに、$\tilde{\mathcal{O}}(\sqrt{T})$戦略的後悔を引き起こす学習アルゴリズムである。
また、$\tilde{\mathcal{o}}(t^{(d+1)/(d+2)})$ strategic regret(ここで$d$は文脈の次元である)のコストで、敵対的なchosenエージェントを処理できるアルゴリズムを与える。
私たちのアルゴリズムは、プリンシパルがバンディットフィードバックを受け取る設定に容易に適応することができます -- この設定は、(インセンティブのあるエージェントを考えることによって)線形文脈バンディット問題と(部分的なフィードバックを可能にすることによって)戦略的分類問題の両方を一般化します。
関連論文リスト
- Paths to Equilibrium in Games [6.812247730094933]
我々は、強化学習におけるポリシー更新に触発されたペアワイズ制約を満たす戦略の列について研究する。
我々の分析は、戦略的な更新を劣化させる報酬が、満足のいく道に沿って均衡に進むための鍵である、という直感的な洞察を明らかにした。
論文 参考訳（メタデータ） (2024-03-26T19:58:39Z) - Strategically-Robust Learning Algorithms for Bidding in First-Price Auctions [11.988955088595858]
ゲーム理論と機械学習のインターフェースにおいて,プライスオークションを繰り返し競うことの学習は基本的な問題である。
本稿では,プライスオークションにおける純ストラテジー入札のための新しいコンケーブの定式化を提案し,この問題に対する自然なグラディエント・アセンセント・アルゴリズムの解析に利用した。
論文 参考訳（メタデータ） (2024-02-12T01:33:33Z) - One-Shot Strategic Classification Under Unknown Costs [19.390528752448283]
幅広いコストに対して、コスト関数の小さな誤推定でさえ、最悪の場合、自明な正確さを伴っていることを示す。
分析の結果,重要な戦略的応答,特にコスト操作関数に対する二重正則化の値が明らかになった。
論文 参考訳（メタデータ） (2023-11-05T20:43:08Z) - Learning to Incentivize Information Acquisition: Proper Scoring Rules
Meet Principal-Agent Model [64.94131130042275]
インセンティブ付き情報取得問題について検討し、主治官がエージェントを雇って代理情報を収集する。
UCBアルゴリズムをモデルに適合させる,実証可能なサンプル効率の良いアルゴリズムを設計する。
本アルゴリズムは,主役の最適利益に対する微妙な推定手順と,所望のエージェントの行動にインセンティブを与える保守的な補正手法を特徴とする。
論文 参考訳（メタデータ） (2023-03-15T13:40:16Z) - Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret
Learning in Markov Games [95.10091348976779]
我々はマルコフゲームにおいて、非定常的でおそらく敵対的な相手と遊べる単一のエージェントを制御する分散ポリシー学習について研究する。
我々は、新しいアルゴリズム、アンダーラインデ集中型アンダーラインハイプラインRpolicy munderlineIrror deunderlineScent (DORIS)を提案する。
DORISは、一般的な関数近似の文脈で$sqrtK$-regretを達成する。
論文 参考訳（メタデータ） (2022-06-03T14:18:05Z) - Who Leads and Who Follows in Strategic Classification? [82.44386576129295]
戦略分類における役割の順序は、決定者とエージェントが互いの行動に適応する相対周波数によって決定される。
更新頻度を自由に選択できる意思決定者は,いずれの順番でスタックルバーグ均衡に収束する学習力学を誘導できることを示す。
論文 参考訳（メタデータ） (2021-06-23T16:48:46Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。
本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
論文 参考訳（メタデータ） (2020-06-11T16:18:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。