論文の概要: Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond

• arxiv url: http://arxiv.org/abs/2503.01701v1
• Date: Mon, 03 Mar 2025 16:13:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:14:13.180464
• Title: Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond
• Title（参考訳）: 線形リワードに対するレギュレット最小化:契約、オークションなど
• Authors: Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti,
• Abstract要約: 本稿では,一括線形報酬に対する後悔の最小化に取り組むための一般的なオンライン学習フレームワークを提案する。 我々のアルゴリズムは$widetildeO(sqrtnT)$を後悔しており、$n$は報酬関数のピース数、$T$はラウンド数である。 第2に,提案アルゴリズムは,ポストプライスオークションにおける価格設定の学習において,適切な(かつ望ましい)インスタンス非依存の後悔境界を達成できることを実証する。
• 参考スコア（独自算出の注目度）: 37.92189925462977
• License:
• Abstract: Most microeconomic models of interest involve optimizing a piecewise linear function. These include contract design in hidden-action principal-agent problems, selling an item in posted-price auctions, and bidding in first-price auctions. When the relevant model parameters are unknown and determined by some (unknown) probability distributions, the problem becomes learning how to optimize an unknown and stochastic piecewise linear reward function. Such a problem is usually framed within an online learning framework, where the decision-maker (learner) seeks to minimize the regret of not knowing an optimal decision in hindsight. This paper introduces a general online learning framework that offers a unified approach to tackle regret minimization for piecewise linear rewards, under a suitable monotonicity assumption commonly satisfied by microeconomic models. We design a learning algorithm that attains a regret of $\widetilde{O}(\sqrt{nT})$, where $n$ is the number of ``pieces'' of the reward function and $T$ is the number of rounds. This result is tight when $n$ is \emph{small} relative to $T$, specifically when $n \leq T^{1/3}$. Our algorithm solves two open problems in the literature on learning in microeconomic settings. First, it shows that the $\widetilde{O}(T^{2/3})$ regret bound obtained by Zhu et al. [Zhu+23] for learning optimal linear contracts in hidden-action principal-agent problems is not tight when the number of agent's actions is small relative to $T$. Second, our algorithm demonstrates that, in the problem of learning to set prices in posted-price auctions, it is possible to attain suitable (and desirable) instance-independent regret bounds, addressing an open problem posed by Cesa-Bianchi et al. [CBCP19].
• Abstract（参考訳）: 興味のあるほとんどのミクロ経済学モデルは、片方向の線形関数を最適化することを含む。 これには、隠れアクションのプリンシパルエージェント問題における契約設計、ポストプライスオークションでの商品の販売、ファーストプライスオークションでの入札が含まれる。 関連するモデルパラメータが未知で、いくつかの(未知の)確率分布によって決定されると、問題は未知かつ確率的な線形報酬関数の最適化方法を学ぶようになる。 そのような問題は、通常、オンライン学習フレームワークに枠を組む。そこでは、意思決定者(学習者)は、後見で最適な決定を知らないという後悔を最小化しようとする。 本稿では,マイクロ経済モデルで共通に満たされる一律性仮定の下で,一括線形報酬の最小化を最小化するための統一的なアプローチを提供する一般オンライン学習フレームワークを提案する。 我々は、$\widetilde{O}(\sqrt{nT})$を後悔する学習アルゴリズムを設計し、$n$は報酬関数の ``pieces'' の数であり、$T$はラウンドの数である。 この結果は、$n$ が $T$ に対して \emph{small} であるとき、特に $n \leq T^{1/3}$ の場合、厳密である。 我々のアルゴリズムは、ミクロ経済環境での学習に関する文献の2つのオープンな問題を解く。 第一に、Zhu et al [Zhu+23] によって得られた$\widetilde{O}(T^{2/3})$ regret bound は、隠蔽作用主エージェント問題における最適線形契約を学習するために、エージェントのアクションの数が$T$に対して小さい場合、厳密でないことを示す。 第2に,提案アルゴリズムは,ポストプライスオークションにおける価格設定の学習において,Cesa-Bianchi et al [CBCP19] によるオープンな問題に対処して,適切な(かつ望ましい)インスタンス非依存の後悔境界を達成できることを実証する。

関連論文リスト

• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
  論文  参考訳（メタデータ） (2024-09-12T07:59:10Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Contextual Bandits and Imitation Learning via Preference-Based Active Queries [17.73844193143454]
  本研究では,学習者が実行された行動報酬の直接的な知識を欠いている文脈的包帯と模倣学習の問題を考察する。 その代わり、学習者は各ラウンドのエキスパートに積極的に問い合わせて2つのアクションを比較し、ノイズの多い好みのフィードバックを受け取ることができる。 学習者の目的は、実行されたアクションに関連する後悔を最小限に抑えると同時に、専門家が行った比較クエリの数を最小化することである。
  論文  参考訳（メタデータ） (2023-07-24T16:36:04Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
  いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。 具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。 効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
  論文  参考訳（メタデータ） (2021-05-28T16:01:42Z)
• Multinomial Logit Contextual Bandits: Provable Optimality and Practicality [15.533842336139063]
  パラメータが不明な多項式ロギット(MNL)選択モデルによってユーザ選択が与えられる順序選択選択問題を検討する。 本稿では,このMNLコンテクストバンディットに対する高信頼境界に基づくアルゴリズムを提案する。 本稿では,アルゴリズムの単純な変種が,幅広い重要なアプリケーションに対して最適な後悔を与えることを示す。
  論文  参考訳（メタデータ） (2021-03-25T15:42:25Z)
• 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 Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。