.png){kind=icon}
返回
Lower Bounds for Ranking-Based Pivot Rules
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.31.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
线性规划单纯形法的多项式枢轴规则、马尔可夫决策过程的策略迭代以及奇偶性博弈的策略改进各自都是其相应领域中的重要开放问题。尽管许多高效规则的天然候选已被排除，但所有现有的下界构造都是针对单个或少数枢轴规则定制的。我们引入了一个统一框架，用于根据规则所依赖的输入信息形式化规则类。在此框架内，我们为基于排序的规则类建立了下界，这些规则基于底层数据诱导的改进枢轴步骤的排序来做出决策。我们的第一个结果是策略改进的一个超多项式下界，通过一类汇点奇偶性博弈获得，适用于仅通过比较某些全局顺序中改进边的秩来访问输入的记忆基Bland规则泛化。我们的第二个结果是策略迭代的一个亚指数下界，通过一类马尔可夫决策过程获得，适用于仅通过比较全局顺序中改进动作的秩、其约简成本以及目标值的关联改进来访问输入的无记忆规则。这两个结果同样适用于线性规划的单纯形法。
Keyword:
lower bounds
Markov decision processes
parity games
pivot rules
policy iteration
simplex method
期刊
机构
查看更多机构
引用论文
暂无论文信息