論文の概要: The Sample Complexity of Online Contract Design
- arxiv url: http://arxiv.org/abs/2211.05732v3
- Date: Fri, 19 May 2023 23:18:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 05:17:58.164325
- Title: The Sample Complexity of Online Contract Design
- Title（参考訳）: オンライン契約設計のサンプル複雑さ
- Authors: Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao,
and Michael I. Jordan
- Abstract要約: オンライン環境での隠れアクションの主エージェント問題について検討する。
各ラウンドにおいて、主席は、各結果に基づいてエージェントへの支払いを指定する契約を投稿する。
エージェントは、自身のユーティリティを最大化する戦略的な行動選択を行うが、プリンシパルによって直接観察できない。
- 参考スコア（独自算出の注目度）: 120.9833763323407
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the hidden-action principal-agent problem in an online setting. In
each round, the principal posts a contract that specifies the payment to the
agent based on each outcome. The agent then makes a strategic choice of action
that maximizes her own utility, but the action is not directly observable by
the principal. The principal observes the outcome and receives utility from the
agent's choice of action. Based on past observations, the principal dynamically
adjusts the contracts with the goal of maximizing her utility.
We introduce an online learning algorithm and provide an upper bound on its
Stackelberg regret. We show that when the contract space is $[0,1]^m$, the
Stackelberg regret is upper bounded by $\widetilde O(\sqrt{m} \cdot
T^{1-1/(2m+1)})$, and lower bounded by $\Omega(T^{1-1/(m+2)})$, where
$\widetilde O$ omits logarithmic factors. This result shows that
exponential-in-$m$ samples are sufficient and necessary to learn a near-optimal
contract, resolving an open problem on the hardness of online contract design.
Moreover, when contracts are restricted to some subset $\mathcal{F} \subset
[0,1]^m$, we define an intrinsic dimension of $\mathcal{F}$ that depends on the
covering number of the spherical code in the space and bound the regret in
terms of this intrinsic dimension. When $\mathcal{F}$ is the family of linear
contracts, we show that the Stackelberg regret grows exactly as
$\Theta(T^{2/3})$.
The contract design problem is challenging because the utility function is
discontinuous. Bounding the discretization error in this setting has been an
open problem. In this paper, we identify a limited set of directions in which
the utility function is continuous, allowing us to design a new discretization
method and bound its error. This approach enables the first upper bound with no
restrictions on the contract and action space.
- Abstract（参考訳）: 隠れアクションの主エージェント問題をオンライン環境で研究する。
各ラウンドにおいて、プリンシパルは、各結果に基づいてエージェントへの支払いを規定する契約をポストする。
エージェントは自身の効用を最大化する戦略的な行動の選択を行うが、その行動はプリンシパルによって直接観測できない。
校長は結果を観察し、エージェントの行動選択からユーティリティを受け取る。
過去の観察に基づいて、プリンシパルは契約を動的に調整し、実用性を最大化する。
オンライン学習アルゴリズムを導入し、Stackelbergの後悔に対する上限を提供する。
契約空間が$[0,1]^m$の場合、Stackelbergの後悔は$\widetilde O(\sqrt{m} \cdot T^{1-1/(2m+1)})$で上界、$\Omega(T^{1-1/(m+2)})$で下界であり、$\widetilde O$は対数要素を省略する。
この結果から,指数-in-m$サンプルは最適に近い契約を学習するのに十分であり,オンライン契約設計の難易度に関する未解決問題を解き明かした。
さらに、契約がいくつかの部分集合 $\mathcal{f} \subset [0,1]^m$ に制限されるとき、空間内の球面コードの被覆数に依存し、この内在的な次元の観点で後悔を束縛する、内在的な次元$\mathcal{f}$ を定義する。
$\mathcal{F}$ が線型契約の族であるとき、Stackelberg の後悔はちょうど $\Theta(T^{2/3})$ として成長することを示す。
ユーティリティ関数が不連続であるため、コントラクト設計の問題は難しい。
この設定における離散化誤差の境界はオープンな問題である。
本稿では,ユーティリティ関数が連続した方向の限定的なセットを同定し,新しい離散化法を設計し,その誤差を限定する。
このアプローチは、コントラクトとアクション空間に制限を伴わない、最初の上限を許容する。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳（メタデータ） (2023-05-27T20:08:35Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Accommodating Picky Customers: Regret Bound and Exploration Complexity
for Multi-Objective Reinforcement Learning [43.75491612671571]
目的と目的のバランスをとる多目的強化学習について、好みを用いて検討する。
我々はこの問題をマルコフ決定過程における叙述的学習問題として定式化する。
モデルに基づくアルゴリズムは、最小限の最小限のリセットを$widetildemathcalObigl(sqrtmind,Scdot H3 SA/epsilon2bigr)$とする。
論文 参考訳（メタデータ） (2020-11-25T21:45:04Z) - Differentially Private Online Submodular Maximization [16.422215672356167]
差分プライバシフィード(DP)を用いた基準制約下でのオンラインサブモジュラー関数の問題点について考察する。
共通有限基底集合上の$T$サブモジュラー関数のストリームがオンラインに届き、各時点において、決定者は関数を観察する前に$U$のほとんどの$k$要素を選択する必要がある。
意思決定者は、選択された集合で評価された関数に等しい報酬を得るとともに、期待の低い後悔を実現する一連の集合を学習することを目的とする。
論文 参考訳（メタデータ） (2020-10-24T07:23:30Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z) - Logistic Regression Regret: What's the Catch? [3.7311680121118345]
パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。
L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
論文 参考訳（メタデータ） (2020-02-07T18:36:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。