論文の概要: Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
- arxiv url: http://arxiv.org/abs/2607.22935v1
- Date: Fri, 24 Jul 2026 22:20:44 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-28 22:34:14.933951
- Title: Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
- Title（参考訳）: 静的および時変露光床を有する離散性有界フェアバンド
- Abstract要約: 露光フロアを正確に調べて、正しい物体が丸みを帯びた問題であることを示す。
主な貢献は、時間によって異なるフロアを持つブロックワイズモデルである。
合成床、MovieLens-100kジャンルの露出、および展開ストレステストの実験は、ペナルティチューニングなしで正確に実現可能であることを示した。
- 参考スコア（独自算出の注目度）: 7.100140700856556
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Minimum-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector. The main contribution is a blockwise model with time-varying floors. BDQ-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budget $R$, not the horizon $T$, with high-probability regret $O(\sqrt{KR\log(KT)})$. A MOSS residual variant attains $O(\sqrt{KR})$, and a matching lower bound gives the minimax rate $Θ(\sqrt{KR})$, even with positive mandatory exposure; a kl-UCB$^{++}$ residual rule adds instance-dependent optimality. The formulation becomes essential for overlapping group floors: per-arm rounding can violate a group constraint by $Ω(s)$ in the group size, whereas Beck--Fiala null-space rounding meets every group floor within the block budget with violation below the arm degree $t$, and composes with UCB at the same $R$-parametrized regret. For learned group plans, we close disjoint systems at $\widetildeΘ(\sqrt{KT})$, give a dual-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan-sampling rule that is pathwise feasible under an initial cover-slack condition and attains a conditional $\widetilde O(\sqrt{KT})$ guarantee, leaving the condition-free overlap rate open. Experiments on synthetic floors, MovieLens-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines.
- Abstract（参考訳）: 最小露光制約は、各プロバイダ、アーム、グループにアグリゲーションだけでなく、期間内に保証された露光を受けなければならない場合に、推奨、コンテンツキュレーション、規制されたアロケーションによって生じる。
我々は,正確な露光床を持つ確率的包帯について検討し,その被写体が丸みを帯びた問題であることを示す: 分数的公正スケジュールは積分プルとして実現され,露光誤差はまさに差分ベクトルである。
主な貢献は、時間によって異なるフロアを持つブロックワイズモデルである。
BDQ-UCB はすべてのブロックフロアを決定論的に満足し、非命令的予算$R$、地平線$T$、高い確率的後悔$O(\sqrt{KR\log(KT)})$によって支配される公正な後悔を持つ。
MOSS残差変分は$O(\sqrt{KR})$に達し、一致する下限は、正の強制露光であっても、ミニマックスレート$(\sqrt{KR})$を与える; kl-UCB$^{++}$残差規則は、インスタンス依存の最適性を追加する。
一方、Beck-Fiala null-space ラウンドリングはブロック予算内のすべてのグループフロアとアーム次数$t$以下で一致し、同じR$パラメトリケートされた後悔で UCB と合成する。
学習群計画について、 Disjoint system at $\widetilde(\sqrt{KT})$ を閉じ、なぜ単純指数規則が重なり合うときに失敗するのかを説明する双対レガー分解を与え、初期被覆-スラック条件下でパス的に実現可能なプランサンプリング則を証明し、条件付き$\widetilde O(\sqrt{KT})$ の保証を得る。
合成フロア、MovieLens-100kジャンルの露出、および展開ストレステストの実験は、ペナルティチューニングなしで正確に実現可能であり、チューニングされたラグランジアンベースラインと競合する。
関連論文リスト
- Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Certify or Refuse: A Cross-Model Map for Selective Risk Control with Coverage Floors under Covariate Shift [4.621071191322703]
自動化フロアを導入することで、選択的な予測者が達成したカバレッジを達成できることを示します。
認証は実行可能性フロンティアと2リソースの複雑性マップを取得し、定数まで加算する。
レートは局所的であり、レギュラーフロンティアマージン、局所登録閾値以下、格子条件を必要とする。
論文 参考訳（メタデータ） (2026-08-11T13:10:55Z) - Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts [19.395115096998108]
MED戦略の線形バージョンから着想を得たアルゴリズムであるDri-MEDを紹介する。
Dri-MEDはドリフトや嗜好構造を無視した保守的なベースラインを著しく上回ることを示す。
論文 参考訳（メタデータ） (2026-06-08T17:53:29Z) - Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
KL正規化目標に対するオンライン学習の統計的効率について検討する。
我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
論文 参考訳（メタデータ） (2026-03-02T18:17:33Z) - Learning to Allocate Resources with Censored Feedback [37.26445474395888]
我々は、検閲されたフィードバックの下で、B$の予算をK$の腕に割り当てなければならないオンラインリソース割り当て問題について検討する。
非自明なパラメータ推定と信頼境界を利用する楽観的なアルゴリズムであるRA-UCBを提案する。
そして、実世界のデータセットの実験を通して理論結果を検証する。
論文 参考訳（メタデータ） (2026-02-06T10:04:54Z) - Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems [18.74680577173648]
我々は、学習者が$m$の腕から$m$の腕を正確に選択する、$m$セット半帯域問題の一般的な場合を考える。
また, Fr'echet 摂動を持つFTPL は, 対向的な設定で, $mathcalO(sqrtnm(sqrtdlog(d)+m5/6)$ をほぼ最適に再現できることを示す。
論文 参考訳（メタデータ） (2025-04-09T22:07:01Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳（メタデータ） (2023-01-31T03:49:00Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。