論文の概要: Allocating Divisible Resources on Arms with Unknown and Random Rewards
- arxiv url: http://arxiv.org/abs/2306.16578v2
- Date: Fri, 3 Nov 2023 01:57:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 17:41:24.315061
- Title: Allocating Divisible Resources on Arms with Unknown and Random Rewards
- Title（参考訳）: 未知・ランダム・リワードを持つ腕に異種資源を割り当てる
- Authors: Ningyuan Chen, Wenhao Li
- Abstract要約: 我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。
アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
- 参考スコア（独自算出の注目度）: 25.93048671326331
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider a decision maker allocating one unit of renewable and divisible
resource in each period on a number of arms. The arms have unknown and random
rewards whose means are proportional to the allocated resource and whose
variances are proportional to an order $b$ of the allocated resource. In
particular, if the decision maker allocates resource $A_i$ to arm $i$ in a
period, then the reward $Y_i$ is$Y_i(A_i)=A_i \mu_i+A_i^b \xi_{i}$, where
$\mu_i$ is the unknown mean and the noise $\xi_{i}$ is independent and
sub-Gaussian. When the order $b$ ranges from 0 to 1, the framework smoothly
bridges the standard stochastic multi-armed bandit and online learning with
full feedback. We design two algorithms that attain the optimal gap-dependent
and gap-independent regret bounds for $b\in [0,1]$, and demonstrate a phase
transition at $b=1/2$. The theoretical results hinge on a novel concentration
inequality we have developed that bounds a linear combination of sub-Gaussian
random variables whose weights are fractional, adapted to the filtration, and
monotonic.
- Abstract（参考訳）: 我々は,各期間に再生可能かつ分別可能な資源の1つの単位を,複数のアームで割り当てる意思決定者を考える。
アームには未知およびランダムな報酬があり、その手段は割り当てられたリソースに比例し、その分散は割り当てられたリソースのオーダー$b$に比例する。
特に、ある期間に意思決定者がリソース$a_i$をarm$i$に割り当てると、報酬$y_i$は$y_i(a_i)=a_i \mu_i+a_i^b \xi_{i}$となる。
b$ が 0 から 1 まで変化すると、フレームワークは標準の確率的多腕バンディットとオンライン学習を完全なフィードバックでスムーズに橋渡しする。
最適なギャップ依存とギャップ非依存の残差境界を$b\in [0,1]$で設計し,$b=1/2$で相転移を示す。
理論的な結果は、重みが分数であり、濾過に適応し、単調なサブガウス確率変数の線形結合を境界とする、新しい濃度不等式にかかっている。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Generalized Regret Analysis of Thompson Sampling using Fractional
Posteriors [12.43000662545423]
トンプソンサンプリング(Thompson sample, TS)は、マルチアームバンディット問題を解くアルゴリズムの1つである。
TSの変種である$alpha$-TSを考え、標準的な後続分布の代わりに$alpha$-posteriorまたは$alpha$-posteriorを使用する。
論文 参考訳（メタデータ） (2023-09-12T16:15:33Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z) - Learning the optimal regularizer for inverse problems [1.763934678295407]
線形逆問題 $y=Ax+epsilon$ を考えると、$Acolon Xto Y$ は分離可能なヒルベルト空間 $X$ と $Y$ の間の既知の線型作用素である。
この設定は、デノイング、デブロアリング、X線トモグラフィーなど、画像のいくつかの逆問題を含んでいる。
古典的な正規化の枠組みの中では、正規化関数が優先順位を与えられず、データから学習される場合に焦点を当てる。
論文 参考訳（メタデータ） (2021-06-11T17:14:27Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。