論文の概要: Pseudo-MDPs: A Novel Framework for Efficiently Optimizing Last Revealer Seed Manipulations in Blockchains

• arxiv url: http://arxiv.org/abs/2510.07080v1
• Date: Wed, 08 Oct 2025 14:39:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.56422
• Title: Pseudo-MDPs: A Novel Framework for Efficiently Optimizing Last Revealer Seed Manipulations in Blockchains
• Title（参考訳）: Pseudo-MDPs: ブロックチェーンにおける最後のリーベラー種子操作を効率的に最適化するための新しいフレームワーク
• Authors: Maxime Reynouard,
• Abstract要約: 本研究では,マルコフ決定過程(MDP)を限定クラスで解く際の計算課題に取り組む。 これはLast Revealer Attack (LRA)によって動機付けられ、資本化(B Market)のようなPoS(Proof-of-Stake)ブロックチェーンの公平性を損なう。 疑似MDP(pMDP)は,このような問題を自然にモデル化し,標準的なMDPに2つの異なる問題を還元するフレームワークである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This study tackles the computational challenges of solving Markov Decision Processes (MDPs) for a restricted class of problems. It is motivated by the Last Revealer Attack (LRA), which undermines fairness in some Proof-of-Stake (PoS) blockchains such as Ethereum (\$400B market capitalization). We introduce pseudo-MDPs (pMDPs) a framework that naturally models such problems and propose two distinct problem reductions to standard MDPs. One problem reduction provides a novel, counter-intuitive perspective, and combining the two problem reductions enables significant improvements in dynamic programming algorithms such as value iteration. In the case of the LRA which size is parameterized by $\kappa$ (in Ethereum's case $\kappa$= 325), we reduce the computational complexity from $O(2^\kappa \kappa^{2^{\kappa+2}})$ to $O(\kappa^4)$ (per iteration). This solution also provide the usual benefits from Dynamic Programming solutions: exponentially fast convergence toward the optimal solution is guaranteed. The dual perspective also simplifies policy extraction, making the approach well-suited for resource-constrained agents who can operate with very limited memory and computation once the problem has been solved. Furthermore, we generalize those results to a broader class of MDPs, enhancing their applicability. The framework is validated through two case studies: a fictional card game and the LRA on the Ethereum random seed consensus protocol. These applications demonstrate the framework's ability to solve large-scale problems effectively while offering actionable insights into optimal strategies. This work advances the study of MDPs and contributes to understanding security vulnerabilities in blockchain systems.
• Abstract（参考訳）: 本研究では,マルコフ決定過程(MDP)を限定クラスで解く際の計算課題に取り組む。 これは、Ethereum($400B)のようなProof-of-Stake(PoS)ブロックチェーンの公平性を損なうLast Revealer Attack(LRA)によって動機付けられている。 疑似MDP(pMDP)は,このような問題を自然にモデル化し,標準的なMDPに2つの異なる問題を還元するフレームワークである。 1つの問題削減は、新しい、反直観的な視点を提供し、2つの問題削減を組み合わせることで、値反復のような動的プログラミングアルゴリズムを大幅に改善することができる。 LRAの場合、サイズは$\kappa$(Ethereumの場合$\kappa$=325)でパラメータ化されますが、計算複雑性を$O(2^\kappa \kappa^{2^{\kappa+2}})から$O(\kappa^4)$(per iteration)に減らします。 このソリューションはまた、動的プログラミングソリューションの通常の利点も提供します。 デュアルパースペクティブはまた、ポリシー抽出を単純化し、この問題が解決されると、非常に限られたメモリと計算で操作できるリソース制約されたエージェントに適している。 さらに,これらの結果をより広範なMDPに一般化し,適用性を高めた。 このフレームワークは、架空のカードゲームとEthereumランダムシードコンセンサスプロトコル上のLRAという2つのケーススタディを通じて検証されている。 これらのアプリケーションは、最適な戦略に関する実用的な洞察を提供しながら、大規模な問題を効果的に解決するフレームワークの能力を示す。 この研究はMDPの研究を前進させ、ブロックチェーンシステムのセキュリティ脆弱性の理解に貢献する。

関連論文リスト

• MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
  半構造化された空間は、M$M$の重みからN$の要素を戦略的に保持することで、有望なソリューションを提供する。 既存の(N:M)互換のアプローチは通常、かなりのエラーに悩まされるルールベースの階層的な欲求探索と、禁止的なトレーニングコストを引き起こす勾配駆動学習の2つのカテゴリに分類される。 MaskProという新しい線形空間確率的フレームワークを提案する。これは、M$連続重みごとに事前のカテゴリー分布を学習し、その後、この分布を活用して(N:M)スパーシリティを$N$-wayサンプリングを通じて生成することを目的としている。
  論文  参考訳（メタデータ） (2025-06-15T15:02:59Z)
• Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
  Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。 本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。 本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
  論文  参考訳（メタデータ） (2024-10-03T07:44:40Z)
• No-Regret Reinforcement Learning in Smooth MDPs [24.249446550171307]
  本稿では,これまで提案されてきたほとんどの設定を一般化した,決定プロセス(MDP)に関する新たな構造仮定を提案する。 本稿では,2つのアルゴリズムを用いて,$nu-$smoothnessにおける後悔の最小化を提案する。 結果とRL理論の最先端技術を比較し,アルゴリズムが最高の保証を達成することを示す。
  論文  参考訳（メタデータ） (2024-02-06T08:18:14Z)
• Optimization for Robustness Evaluation beyond $\ell_p$ Metrics [11.028091609739738]
  敵対的攻撃に対するディープラーニングモデルの実証的評価は、非自明な制約付き最適化問題を解くことを伴う。 本稿では,PyGRANSO, With Constraint-Folding (PWCF) をブレンドして信頼性と汎用性を向上するフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-10-02T20:48:05Z)
• Efficient Policy Iteration for Robust Markov Decision Processes via Regularization [49.05403412954533]
  ロバストな意思決定プロセス(MDP)は、システムのダイナミクスが変化している、あるいは部分的にしか知られていない決定問題をモデル化するためのフレームワークを提供する。 最近の研究は、長方形長方形の$L_p$頑健なMDPと正規化されたMDPの等価性を確立し、標準MDPと同じレベルの効率を享受する規則化されたポリシー反復スキームを導出した。 本研究では、政策改善のステップに焦点をあて、欲求政策と最適なロバストなベルマン作用素のための具体的な形式を導出する。
  論文  参考訳（メタデータ） (2022-05-28T04:05:20Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。 そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
  論文  参考訳（メタデータ） (2020-03-11T23:23:29Z)

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

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