Dec, 2021

交互式决策的统计复杂度

PDF
TL;DR提供决策 - 评估系数，作为评估交互式学习复杂度的量，从而实现与样本效率无关的最佳后悔，同时引入了一种新的选择 Estimation-to-Decisions（E2D），使得监督学习的算法适应于在线决策，从而实现了准确的与样本效率无关的学习，在强化学习中，该决策 - 评估系数可以快速恢复现有的大多数困难结果和下限。
interactive learningregretsample-efficientestimation-to-decisionsreinforcement learning
发现论文，激发创造
  • 具有决策估计系数的强化学习统一算法：无遗憾、PAC 和无奖励学习

    本文提出 Decision-Estimation Coefficient (DEC) 作为强化学习 (Reinforcement Learning, RL) 中无后悔 RL 的必要和充分的复杂度度量，并提出 Explorative DEC (EDEC) 和 Reward-Free DEC (RFDEC) 作为对 DEC 的扩展，设计了针对三个学习目标的新的统一的样本有效算法。

    Sep, 2022

  • 通过鞍点优化实现遗憾最小化

    通过最小化后悔的样本复杂性，本论文提出了一种基于决策 - 估计系数（DEC）的在线算法，用于优化结构化强化学习和有限模型类的探索 - 利用平衡问题。

    Mar, 2024

  • 交互式估计的统一模型和维度

    本文提出了交互式学习的抽象框架 —— 交互估计，其中目标是通过学习者查询的点与其类似性来估计目标。我们介绍了一种称为不相似维度的组合度量，从很大程度上捕获了我们模型中的可学习性。我们提出了一种简单、通用和广泛适用的算法，对其进行了后悔和 PAC 泛化边界的求解，这些边界在新维度中是多项式的。我们展示了我们的框架涵盖并统一了两个经典的学习模型：统计查询学习和结构化强化学习。我们还说明了不相似维度与两种框架的众所周知的参数的关系，在某些情况下得到了显着改进的分析。

    Jun, 2023

  • 多智体决策的复杂性：从博弈中的学习到部分监控

    本文研究了多智能体强化学习中的样本效率、均衡计算和统计复杂性等问题，提出了一系列新的结构性结果，并阐述了决策时附带隐藏报酬的统计复杂度。

    May, 2023

  • 离线决策的可学习性理论

    我们研究了离线决策问题，通过从仅与学习目标部分相关的数据集中学习决策。为填补现有研究在离线决策问题的统一框架和理论方面的不足，我们引入了一个统一框架，称为带离线反馈的决策制定（DMOF），它包括离线强化学习、离策略评估和离线部分可观测马尔可夫决策过程等一系列离线决策问题。对于 DMOF 框架，我们引入了一个称为离线估计系数（OEC）的难度衡量标准，用于衡量离线决策问题的可学习性，并且该标准也反映在导出的极小极大下界中。此外，我们还引入了一种称为经验决策与差异（EDD）的算法，我们为其建立了一个实例相关的上界和极小极大上界，该极小极大上界几乎与 OEC 确定的下界相匹配。最后，我们展示了 EDD 在特定设置下（如监督学习和具有部分覆盖的马尔可夫序列问题（例如 MDPs））实现了快速收敛速度（即按照 $1/N$ 的比例缩放的速度，其中 $N$ 是样本大小）。

    Jun, 2024

  • 交互决策中的实例最优性：走向一个非渐近理论

    本研究旨在开发适应性算法，用于互动决策制定，并在实际状况好的实例中适应性地提高性能。研究提出了 Allocation-Estimation Coefficient (AEC) 的复杂度度量，并提出了新的算法 AE2，它控制了 AEC 的速率，达到非渐近实例优化性能。这些结果补充了较差保证，即现有的统计复杂度概念不足以推导非渐近保证，并且在某些技术条件下，有限时间内学习实例优化决策分配需要限定 AEC。

    Apr, 2023

  • 在线学习与序列复杂度

    研究序列预测的问题，提供工具来研究相关游戏的极小极大值。开发了一套序列复杂性理论，能够准确地为序列预测问题提供学习保证。

    Jun, 2010

  • 在线估计通过离线估计：一种信息论框架

    统计估计的经典理论和在线学习的现代理论相结合，提出了黑盒离线估计到在线估计的转化问题，通过引入 Oracle-Efficient Online Estimation (OEOE) 框架，从信息论的角度解决了在线估计的统计复杂性和计算复杂性，并将结果应用于交互决策制定。

    Apr, 2024

  • 基于统一 PAC-Bayesian-Rademacher-Shtarkov-MDL 复杂度的紧致过量风险界

    提出了一种新的学习理论复杂性概念，它在经验风险最小化和贝叶斯估计器的情况下分别以数据无关的 Rademacher 复杂度和数据相关的信息复杂度进行上限绑定，并通过 Rademacher 复杂度将其与 $L_2 (P)$ 熵进行关联。该研究进一步使用 ' 易于理解 ' 和模型复杂性等相互分离的方法，提供适用于 VC 和多项式熵类的最优性差距上限。

    Oct, 2017

  • 信息约束在线学习中的适应性

    研究了如何适应信息获取成本昂贵的在线学习问题中平稳变化环境的影响；提出了一种算法用于处理标签有效预测的问题，并扩展到标签有效的赌博反馈和揭示行动部分监测游戏等领域，显著提高了现有算法的性能。

    Oct, 2019