Jun, 2024

具有下层背景上下文的随机双层优化与决策过程

PDF
TL;DR我们介绍了一种基于情境马尔可夫决策过程（CMDP）的双层优化策略模型（BO-CMDP），该模型可以看作是领导者和随机情境共同决定多个马尔可夫决策过程（MDP）的设定，在各种应用中寻求最佳决策策略，进而应用于 MDP 模型设计、税务设计、奖励塑造和动态机制设计等领域。我们提出了一种基于梯度下降的随机超级策略（HPGD）算法用于求解 BO-CMDP 问题，并证明了其收敛性。该算法只利用随从者的轨迹观察，使得随从者可以使用任何训练过程而领导者无需了解具体算法，使得该模型适用于各种实际应用场景。我们还考虑了领导者能够影响随从者训练的情形，并提出了一种加速算法。我们通过实验证明了我们算法的性能。
bilevel optimizationcontextual markov decision processesstackelberg gamehyper policy gradient descentdynamic mechanism design
发现论文，激发创造
  • 上下文随机双层优化

    我们引入了上下文随机双层优化（CSBO）—— 一种在下层问题最小化给定某些上下文信息和上层决策变量条件下的期望的随机双层优化框架。该框架扩展了经典的随机双层优化，使得下层决策者不仅对上层决策者的决策做出最优响应，还对一些侧面信息做出响应，并且存在多个甚至无数个追随者。它涵盖了元学习、个性化联邦学习、端到端学习和侧面信息的 Wasserstein 分布鲁棒优化等重要应用。由于存在上下文信息，现有的经典随机双层优化的单循环方法无法收敛。为了克服这个挑战，我们引入了一种基于多层蒙特卡罗（MLMC）技术的高效双循环梯度方法，并建立了其样本复杂度和计算复杂度。当专门应用于随机非凸优化时，我们的方法与现有下界相匹配。对于元学习，我们的方法的复杂度不依赖于任务数量。数值实验进一步验证了我们的理论结果。

    Oct, 2023

  • 上下文马尔可夫决策过程

    论文讨论了一种名为 CMDP 的新模型，可模拟顾客在与网站交互时的行为，并基于此行为决定顾客特征，优化交互。作者提出了一系列算法，可以学习潜在的模型和上下文，并优化 CMDPs。

    Feb, 2015

  • 约束马尔可夫决策过程的原始对偶方法

    本文提出了一种基于采样的原始 - 对偶算法来解决带约束的马尔科夫决策过程，通过应用正则化策略迭代来改善策略，应用次梯度上升来保持约束。在弱耦合结构的情况下，通过嵌入式分解方法，能够显著减少问题的维度。将算法应用于多产品库存管理和多类队列调度，并表明它产生优于现有启发式算法的控制。

    Jan, 2021

  • 具有历史依赖的动态环境下的强化学习

    本研究介绍了一种新的强化学习框架：动态上下文马尔可夫决策过程（DCMDPs），着重关注于处理非马尔可夫环境的情况。该模型利用聚合函数确定上下文转换，使得指数与历史长度的依赖关系得到破解。作者还展现了在基于该模型的算法上的实现效果。实验根据 MovieLens 数据开展，主要探讨了针对推荐任务变化的用户行为的模式研究

    Feb, 2023

  • 基于分层探索 - 利用权衡的离线 Oracle 高效学习上下文 MDP

    本文提出了一种从上下文马尔科夫决策过程到离线密度估计的高效、近似最优的转化算法，同时解决了无结构假设的模型类 CMDPs。

    May, 2024

  • 线性情境马尔可夫决策过程的样本复杂度刻画

    该论文研究了上下文马尔可夫决策过程（CMDPs）在线性函数逼近模型下的性质，提出了创新的基于模型的算法，并证明了其在样本复杂度方面的优越性。比较两种模型的结果表明，上下文变化的特征比所有上下文共享表示在线性 CMDPs 中具有更好的样本效率。

    Feb, 2024

  • 贝叶斯策略优化模型不确定性

    解决不确定性对于自主系统在现实世界中的可靠适应至关重要。我们提出了一种模型不确定性的连续 Bayes-Adaptive Markov Decision Process（BAMDP）算法，其中代理人维护潜在模型参数的后验分布，并相对于该信念分布最大化其预期长期回报。我们的算法建立在最新的策略优化算法之上，以学习通用策略，以最大化贝叶斯价值函数的探索 - 开发权衡。为了应对从离散化连续潜在参数空间带来的挑战，我们提出了一种新的策略网络体系结构，可将信念分布独立于可观察状态地编码。我们的方法显着优于没有明确考虑信念分布而解决模型不确定性的算法，并且与现有的部分可观测马尔可夫决策过程求解器竞争力相当。

    Oct, 2018

  • 具有连续侧信息的马尔可夫决策过程

    本文提出了一种基于上下文的马尔可夫决策过程增强学习算法，用于医疗保健中的治疗决策。算法基于平滑性假设进行学习，并给出了 PAC 边界。在上下文可线性组合的情况下，基于 KWIK 学习技术，我们提供了一个 PAC 学习算法。

    Nov, 2017

  • 使用双层马尔可夫决策过程进行空间任务的应急计划

    该研究侧重于科学任务的自主应变规划，通过允许从状态空间的任何非正常点快速计算决策，以应对与正常任务计划的延误或偏离。通过提出双层马尔可夫决策过程（MDP）框架，改进了计算可处理性，同时与现有任务规划实践相吻合并增强了基于人工智能的解决方案的可解释性和可信度，通过将任务规划 MDP 转化为双层 MDP 来讨论了这一框架，并在 RoverGridWorld 上对其进行了测试，这是一个用于漫游任务规划的改进的 GridWorld 环境。我们展示了使用双层 MDP 方法实现的计算可处理性和近似最佳策略，突出了问题复杂性增加时计算时间和政策最优性之间的权衡。这项研究有助于更高效和灵活地应对科学任务的应变规划。

    Feb, 2024

  • 学习具有随机硬约束的对抗式马尔可夫决策过程

    我们研究带有对抗性损失和随机硬约束的约束马尔可夫决策过程（CMDP）中的在线学习问题。我们设计了两种不同的情景，第一种是在一般 CMDP 中实现次线性遗憾和累积正约束违规的算法。第二种情景下，我们假设策略存在且对学习者已知，并设计了一个算法，确保次线性遗憾的同时，高概率满足所有回合的约束。据我们所知，我们的工作是第一个研究同时涉及对抗性损失和硬约束的 CMDP。这些算法可处理一般非平稳环境中的要求，要求比现有算法处理的要严格得多，从而能够在更广范围的实际应用中采用，包括自动驾驶、在线广告和推荐系统。

    Mar, 2024