Fugu-MT 論文翻訳(概要): Super-Exponential Regret for UCT, AlphaGo and Variants

論文の概要: Super-Exponential Regret for UCT, AlphaGo and Variants

arxiv url: http://arxiv.org/abs/2405.04407v1
Date: Tue, 7 May 2024 15:35:30 GMT
ステータス: 処理完了
システム内更新日: 2024-05-08 13:31:20.831306
Title: Super-Exponential Regret for UCT, AlphaGo and Variants
Title（参考訳）: UCT, AlphaGo, Variantsの超指数レジストレーション
Authors: Laurent Orseau, Remi Munos,
Abstract要約: 私たちは、UDTが$D$-chain環境上で$exp(dotsexp(1)dots)$ regret($Omega(D)$ exp terms)を持つことを示します。また、この証明をAlphaGoのMCTSとその子孫に適用する。
参考スコア（独自算出の注目度）: 5.49097855598435
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We improve the proofs of the lower bounds of Coquelin and Munos (2007) that demonstrate that UCT can have $\exp(\dots\exp(1)\dots)$ regret (with $\Omega(D)$ exp terms) on the $D$-chain environment, and that a `polynomial' UCT variant has $\exp_2(\exp_2(D - O(\log D)))$ regret on the same environment -- the original proofs contain an oversight for rewards bounded in $[0, 1]$, which we fix in the present draft. We also adapt the proofs to AlphaGo's MCTS and its descendants (e.g., AlphaZero, Leela Zero) to also show $\exp_2(\exp_2(D - O(\log D)))$ regret.
Abstract（参考訳）: We improve the proofs of the lower bounds of Coquelin and Munos (2007) that demonstrate that UCT can have $\exp(\dots\exp(1)\dots)$ regret (with $\Omega(D)$ exp terms) on the $D$-chain environment and that `polynomial' UCT variant have $\exp_2(\exp_2(D - O(\log D)))$ regret on the same environment -- the original proofs contains an oversight for rewards bounded in $[0, 1]$。また、AlphaGoのMCTSとその子孫(例えば、AlphaZero、Leela Zero)にも証明を適用して、$\exp_2(\exp_2(D - O(\log D)))$ regretを示す。

関連論文リスト

Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文参考訳（メタデータ） (2024-06-18T08:54:04Z)
$α$-$z$-Rényi divergences in von Neumann algebras: data-processing inequality, reversibility, and monotonicity properties in $α,z$ [2.3020018305241337]
本稿では,$alpha$-$z$-R'enyi の変分表現とデータ処理の不等式(DPI)を証明した。パラメータ $alpha,z$ における $D_alpha,z(psi|varphi)$ の単調性特性とその正規化相対エントロピーに対する極限を示す。
論文参考訳（メタデータ） (2024-04-11T10:10:08Z)
$\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文参考訳（メタデータ） (2023-07-11T08:51:53Z)
On the Minimax Regret for Online Learning with Feedback Graphs [5.721380617450645]
強く観察可能な無向フィードバックグラフを用いて,オンライン学習を後悔する上で,上層と下層の境界を改善した。改良された上界$mathcalObigl(sqrtalpha T(ln K)/(lnalpha)bigr)$ hold for any $alpha$ and the lower bounds for bandits and experts。
論文参考訳（メタデータ） (2023-05-24T17:40:57Z)
Does Sparsity Help in Learning Misspecified Linear Bandits? [32.920577630673804]
アルゴリズムは$O(varepsilon-sds)$アクションをクエリすることで、$O(varepsilon)$-optimalアクションを得ることができることを示す。また、サンプルの複雑さに対する上限は、エラーが$O(sdeltavarepsilon)$$$0delta1$を要求する場合、ほぼ厳密であることを示す。
論文参考訳（メタデータ） (2023-03-29T19:58:39Z)
Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
論文参考訳（メタデータ） (2022-05-19T18:51:28Z)
Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文参考訳（メタデータ） (2021-09-21T13:19:04Z)
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case [5.88864611435337]
大型アルファベット上で定義される行列値関数に対する超収縮的不等式を証明した。逆数モデルの全てのストリーミングアルゴリズムが$(r-varepsilon)$-approximationを達成するためには、$Omega(n1-2/t)$量子空間が必要である。
論文参考訳（メタデータ） (2021-09-06T16:56:19Z)
Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文参考訳（メタデータ） (2021-03-25T18:52:17Z)
Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文参考訳（メタデータ） (2021-02-15T08:16:51Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)

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