論文の概要: Scheduling with Uncertain Holding Costs and its Application to Content Moderation

• arxiv url: http://arxiv.org/abs/2505.21331v1
• Date: Tue, 27 May 2025 15:26:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-28 17:05:58.757051
• Title: Scheduling with Uncertain Holding Costs and its Application to Content Moderation
• Title（参考訳）: 不確実な保持コストによるスケジューリングとコンテンツモデレーションへの応用
• Authors: Caner Gocmen, Thodoris Lykouris, Deeksha Sinha, Wentao Weng,
• Abstract要約: ソーシャルメディアプラットフォームにおけるコンテンツモデレーションでは、コンテンツのレビューを遅らせるコストは、そのビューの軌跡に比例する。 ジョブ状態が状態依存の即時保持コストを持つマルコフ連鎖に基づいて進化する待ち行列モデルを考える。 我々は,各ジョブをマルコフスキーレンタル問題と見なすことで,不確実性が部分的に解決した場合の将来の求職機会に適応するインデックスベースのアルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 4.2130745016804205
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In content moderation for social media platforms, the cost of delaying the review of a content is proportional to its view trajectory, which fluctuates and is apriori unknown. Motivated by such uncertain holding costs, we consider a queueing model where job states evolve based on a Markov chain with state-dependent instantaneous holding costs. We demonstrate that in the presence of such uncertain holding costs, the two canonical algorithmic principles, instantaneous-cost ($c\mu$-rule) and expected-remaining-cost ($c\mu/\theta$-rule), are suboptimal. By viewing each job as a Markovian ski-rental problem, we develop a new index-based algorithm, Opportunity-adjusted Remaining Cost (OaRC), that adjusts to the opportunity of serving jobs in the future when uncertainty partly resolves. We show that the regret of OaRC scales as $\tilde{O}(L^{1.5}\sqrt{N})$, where $L$ is the maximum length of a job's holding cost trajectory and $N$ is the system size. This regret bound shows that OaRC achieves asymptotic optimality when the system size $N$ scales to infinity. Moreover, its regret is independent of the state-space size, which is a desirable property when job states contain contextual information. We corroborate our results with an extensive simulation study based on two holding cost patterns (online ads and user-generated content) that arise in content moderation for social media platforms. Our simulations based on synthetic and real datasets demonstrate that OaRC consistently outperforms existing practice, which is based on the two canonical algorithmic principles.
• Abstract（参考訳）: ソーシャルメディアプラットフォームにおけるコンテンツモデレーションでは、コンテンツのレビューを遅らせるコストは、そのビューの軌跡に比例する。 このような不確実な保持コストを動機として、状態依存の瞬時保持コストを持つマルコフ連鎖に基づいてジョブ状態が進化する待ち行列モデルを考える。 このような不確実な保持コストの存在下では、2つの正準アルゴリズム原則、即時コスト(c\mu$-rule)と期待残コスト(c\mu/\theta$-rule)が最適であることを示す。 我々は,各ジョブをマルコフスキーレンタル問題と見なすことで,不確実性が部分的に解決した場合に求職機会を調整した新たなインデックスベースアルゴリズムであるオポチュニティ調整型残留コスト(OaRC)を開発した。 OaRCの後悔は$\tilde{O}(L^{1.5}\sqrt{N})$で、$L$はジョブの保持コスト軌跡の最大長であり、$N$はシステムサイズである。 この後悔の限界は、システムサイズが無限大までスケールすると、OaRCが漸近的最適性を達成することを示している。 さらに、その後悔は、ジョブ状態がコンテキスト情報を含む場合に望ましいプロパティである状態空間サイズとは独立している。 ソーシャルメディアプラットフォームにおけるコンテンツモデレーションにおいて生じる2つの保持コストパターン(オンライン広告とユーザ生成コンテンツ)に基づく広範なシミュレーション研究により、その結果を裏付ける。 合成および実データセットに基づくシミュレーションにより、OaRCは2つの正準アルゴリズム原理に基づく既存のプラクティスより一貫して優れていることが示された。

関連論文リスト

• Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints [11.029788598491077]
  我々は,サステナビリティとエネルギの新たな課題によって動機付けられた,新たなオンライン問題を紹介し,研究する。 オンラインプレーヤーは$mathsfSOADで、ポイント当たりのメートル法空間$(, d) にアロケートしてスケジューリングすることで、ワークロードを完了します。 各時点において、各時点における作業負荷のコストを表すサービスコスト関数が明らかにされ、プレーヤは、現在の作業のポイントへの割り当てを不当に決定しなければならない。
  論文  参考訳（メタデータ） (2024-08-14T22:08:06Z)
• Learning to Schedule Online Tasks with Bandit Feedback [7.671139712158846]
  オンラインタスクスケジューリングは、クラウドコンピューティングやクラウドソーシングにおけるタスク集約型アプリケーションにおいて重要な役割を果たす。 本稿では,二重最適化学習に基づくRobins-Monro(DOL-RM)アルゴリズムを提案する。 DOL-RMは、報酬対コスト比の楽観的な推定と決定モジュールを組み込んだ学習モジュールを統合する。
  論文  参考訳（メタデータ） (2024-02-26T10:11:28Z)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations [92.25604137490168]
  本稿では,制御系における効率的な強化学習に関する理論的研究を紹介する。 遅延および欠落した観測条件において,RL に対して $tildemathcalO(sqrtrm poly(H) SAK)$ という形でアルゴリズムを提示し,その上限と下限をほぼ最適に設定する。
  論文  参考訳（メタデータ） (2023-06-02T02:46:39Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• Acting in Delayed Environments with Non-Stationary Markov Policies [57.52103323209643]
  本稿では,MDPにおける学習と計画のためのフレームワークについて紹介する。 実行が遅れると、元の状態空間における決定論的マルコフポリシーは最大報酬を得るのに十分であるが、非定常である必要があることを証明します。 我々は、状態拡張に頼らずに遅延実行タスクを解く非定常Q学習スタイルのモデルベースアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2021-01-28T13:35:37Z)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  最短経路 (SSP) は計画と制御においてよく知られた問題である。 また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。 我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
  論文  参考訳（メタデータ） (2020-06-20T12:10:35Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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