論文の概要: SoftTreeMax: Exponential Variance Reduction in Policy Gradient via Tree Search

• arxiv url: http://arxiv.org/abs/2301.13236v1
• Date: Mon, 30 Jan 2023 19:03:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-01 18:44:49.201095
• Title: SoftTreeMax: Exponential Variance Reduction in Policy Gradient via Tree Search
• Title（参考訳）: SoftTreeMax:木探索による政策勾配の指数変数削減
• Authors: Gal Dalal, Assaf Hallak, Gugan Thoppe, Shie Mannor, Gal Chechik
• Abstract要約: 我々は,計画を考慮したソフトマックスの一般化であるSoftTreeMaxを紹介する。 この分散を緩和する上で,木の拡大政策が果たす役割を初めて示す。 我々の分化可能なツリーベースのポリシーは、従来の単一サンプルベースの勾配ではなく、各環境における木の葉のすべての勾配を利用する。
• 参考スコア（独自算出の注目度）: 68.66904039405871
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite the popularity of policy gradient methods, they are known to suffer from large variance and high sample complexity. To mitigate this, we introduce SoftTreeMax -- a generalization of softmax that takes planning into account. In SoftTreeMax, we extend the traditional logits with the multi-step discounted cumulative reward, topped with the logits of future states. We consider two variants of SoftTreeMax, one for cumulative reward and one for exponentiated reward. For both, we analyze the gradient variance and reveal for the first time the role of a tree expansion policy in mitigating this variance. We prove that the resulting variance decays exponentially with the planning horizon as a function of the expansion policy. Specifically, we show that the closer the resulting state transitions are to uniform, the faster the decay. In a practical implementation, we utilize a parallelized GPU-based simulator for fast and efficient tree search. Our differentiable tree-based policy leverages all gradients at the tree leaves in each environment step instead of the traditional single-sample-based gradient. We then show in simulation how the variance of the gradient is reduced by three orders of magnitude, leading to better sample complexity compared to the standard policy gradient. On Atari, SoftTreeMax demonstrates up to 5x better performance in a faster run time compared to distributed PPO. Lastly, we demonstrate that high reward correlates with lower variance.
• Abstract（参考訳）: ポリシー勾配法の人気にもかかわらず、大きなばらつきと高いサンプル複雑さに苦しむことが知られている。 これを軽減するために、我々はSoftTreeMaxを紹介します。 SoftTreeMaxでは、複数段階の累積報酬で従来のロジットを拡張し、将来の状態のロジットを上乗せします。 softtreemax の2つの変種を考える。1つは累積報酬、もう1つは累積報酬である。 いずれの場合も勾配分散を解析し,この分散を緩和する上で,木展開ポリシーの役割を初めて明らかにする。 その結果,展開方針の関数として計画地平線が指数関数的に崩壊することを証明する。 具体的には、結果として生じる状態遷移がより近いほど、崩壊が速くなることを示す。 実用的な実装として,並列gpuベースのシミュレータを用いて高速かつ効率的な木探索を行う。 我々の分化可能なツリーベースのポリシーは、従来の単一サンプルベースの勾配ではなく、各環境における木の葉のすべての勾配を利用する。 次に, 勾配のばらつきを3桁小さくするシミュレーションを行い, 標準政策勾配と比較して, サンプルの複雑さが向上することを示した。 Atariでは、SoftTreeMaxは、分散PPOと比較して、より高速な実行時間で最大5倍のパフォーマンスを示す。 最後に,高い報酬は低い分散と相関することを示す。

関連論文リスト

• MAPTree: Beating "Optimal" Decision Trees with Bayesian Decision Trees [2.421336072915701]
  本稿では,決定木誘導に対するベイズ的アプローチを提案する。 そこで我々は,MAPTreeとよばれるAND/OR探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-26T23:43:37Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  本稿では,離散潜在変数の生成に関わるパラメータの勾配を近似する新しい手法を提案する。 本稿では,Hunの手法とODEを解くための2次数値法を統合することで,2次精度を実現するReinMaxを提案する。
  論文  参考訳（メタデータ） (2023-04-17T20:59:49Z)
• SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
  我々は、ツリー検索をポリシー勾配に統合する最初のアプローチであるSoftTreeMaxを紹介します。 Atariでは、SoftTreeMaxが分散PPOと比較して、実行時のパフォーマンスを最大5倍向上させる。
  論文  参考訳（メタデータ） (2022-09-28T09:55:47Z)
• Social Interpretable Tree for Pedestrian Trajectory Prediction [75.81745697967608]
  本稿では,このマルチモーダル予測課題に対処するため,SIT(Social Interpretable Tree)と呼ばれる木に基づく手法を提案する。 木の根から葉までの経路は、個々の将来の軌跡を表す。 ETH-UCYとStanford Droneのデータセットによる実験結果からは,手作り木にもかかわらず,我々の手法が最先端の手法の性能に適合または超えることを示した。
  論文  参考訳（メタデータ） (2022-05-26T12:18:44Z)
• Lassoed Tree Boosting [53.56229983630983]
  有界断面変動のカドラー関数の大きな非パラメトリック空間において,早期に停止するn-1/4$ L2の収束速度を持つ勾配向上木アルゴリズムを証明した。 我々の収束証明は、ネストしたドンスカー類の経験的損失最小化子による早期停止に関する新しい一般定理に基づいている。
  論文  参考訳（メタデータ） (2022-05-22T00:34:41Z)
• Hierarchical Shrinkage: improving the accuracy and interpretability of tree-based methods [10.289846887751079]
  木構造を改変しないポストホックアルゴリズムである階層収縮(Hierarchical Shrinkage, HS)を導入する。 HSは、他の正規化技術と併用しても、決定木の予測性能を大幅に向上させる。 すべてのコードとモデルはGithubにある本格的なパッケージでリリースされている。
  論文  参考訳（メタデータ） (2022-02-02T02:43:23Z)
• A better method to enforce monotonic constraints in regression and classification trees [0.0]
  回帰木と分類木にモノトン制約を強制する2つの新しい方法を提案する。 1つは現在のLightGBMよりも良い結果をもたらし、同様の計算時間を持つ。 もう1つはより優れた結果をもたらすが、現在のLightGBMよりもずっと遅い。
  論文  参考訳（メタデータ） (2020-11-02T14:04:21Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)

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

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