Apr, 2023

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

PDF
TL;DR本研究旨在开发适应性算法，用于互动决策制定，并在实际状况好的实例中适应性地提高性能。研究提出了 Allocation-Estimation Coefficient (AEC) 的复杂度度量，并提出了新的算法 AE2，它控制了 AEC 的速率，达到非渐近实例优化性能。这些结果补充了较差保证，即现有的统计复杂度概念不足以推导非渐近保证，并且在某些技术条件下，有限时间内学习实例优化决策分配需要限定 AEC。
adaptive algorithmsinstance-dependentdecision makingcomplexity measurefunction approximation
发现论文，激发创造
  • 基于不同实例的情境臂和强化学习复杂度：一种基于反对的视角

    该研究提出了一种用于上下文 Bandit 问题的复杂度度量方法，展示了其与最优实例相关遗憾的关系，并给出了新的算法来实现当存在一个最优选择时能够分辨性地进行探索。同时，该研究还在采用函数近似的强化学习问题上提出了新的算法，达到了优化的样本规模。

    Oct, 2020

  • 超越无悔：实例相关的 PAC 强化学习

    研究提出了一种新的针对 PAC 表格强化学习的实例相关样本复杂度的计算方法，并设计了一种能够达到该样本复杂度的规划算法，该算法几乎是极小值最优的，且在多个实例上展现出比最坏情况界限更显著的改进。

    Aug, 2021

  • 在随机和对抗线性赌博机中同时实现近似实例最优性和极小化最优性

    本文将开发线性试探算法来适应不同的环境，并提出一种新的损失估计方法，该算法在随机环境中实现了几乎实时最优遗憾，还在带有额外遗憾的破损环境中工作，并装备有对抗性组件，同时拥有最小化遗憾的敌对环境优势。

    Feb, 2021

  • 交互式决策的统计复杂度

    提供决策 - 评估系数，作为评估交互式学习复杂度的量，从而实现与样本效率无关的最佳后悔，同时引入了一种新的选择 Estimation-to-Decisions（E2D），使得监督学习的算法适应于在线决策，从而实现了准确的与样本效率无关的学习，在强化学习中，该决策 - 评估系数可以快速恢复现有的大多数困难结果和下限。

    Dec, 2021

  • 上下文赌博机的最优 PAC 算法

    本文研究了 $(\epsilon,\delta)-\textit {PAC}$ 场景下的随机赌博机问题，给出了上下界，并提供了一个新的基于 argmax Oracle 的实例最优和计算效率高的算法。

    Jul, 2022

  • 最优值估计中的实例最优性：通过方差缩减 Q 学习实现自适应

    本文提出一个本地极小极大方法，分析了计算强化学习下的最优 $Q$ 值函数的实例特定行为，并提供一个针对 $Q$ 学习中困难问题和易解问题的有力解释。

    Jun, 2021

  • 时序差分学习是否最优？一种实例相关的分析

    通过引入变量缩减形式的随机逼近，本研究提出了一种实例依赖的策略评估算法，并在非渐近条件下实现了优化性能，同时在理论上证明了其优越性。

    Mar, 2020

  • 何时可以在平均回报无休止赌博中达到指数渐近最优性？

    我们提出了一种新的策略，该策略通过维护两个动态武器子集来解决离散时间无限视界平均奖励不安定强盗问题，其中一个子集具有近乎最优的状态分布并根据最优局部控制例程采取行动；另一个子集被驱向最优状态分布并逐渐合并到第一个子集中。我们证明了我们的策略在满足周期性 - 单链、非退化性和局部稳定性等温和假设的情况下在 N 臂问题中是渐进最优的，并且具有 O (exp (-C N)) 的最优性差距。我们的策略是首个在上述易于验证的假设集下实现指数渐近最优性的方法，而先前的工作要么需要强全局吸引子假设，要么仅实现了 O (1/sqrt (N)) 的最优性差距。我们进一步讨论了在显著减弱假设的基础上面临的基本障碍。特别地，我们通过证明一个下界，证明了局部稳定性对于指数渐近最优性是必要的。

    May, 2024

  • 通过解游戏进行非渐近纯探索

    本文提出了一种适用于纯探索问题和赌博机结构的不需完全解决优化问题的优化算法，并获得了对指数族的适应性和有限信心保证。

    Jun, 2019

  • 非参数通用强化学习

    本文提出了在非 Markovian、非 ergodic 且只部分可观察的环境下进行强化学习的问题。作者建立了贝叶斯强化学习代理的负面结果，并证明 Thompson 采样在随机环境中是渐进最优的。此外，作者构建了一个大但可计算的类，展示了基于 Thompson 采样的代理在这个类中收敛于任意未知可计算多智能体环境中的纳什均衡。

    Nov, 2016