在部分可观测系统中学习接近最优的策略仍然是当代强化学习中一个难以捉摸的挑战。在这项工作中，我们考虑了奖励混合马尔可夫决策过程（MDP）中的情景强化学习。在那里，在每一集开始时，从多个可能的奖励模型中提取一个奖励函数，但所选择的奖励模型的身份不会透露给智能体人。因此，动力学为马尔可夫的潜态空间并没有给予智能体。我们研究了两个奖赏混合MDP学习接近最优策略的问题。与依赖于对动力学的强假设的现有方法不同，我们不做任何假设，而是全面地研究问题。事实上，在没有进一步假设的情况下，即使是对于两个切换奖励模型，这个问题也需要一些新的想法，超越现有的算法和分析技术，以实现有效的探索。我们提供了在探索O（poly（H−1）·S 2A2）集，其中H是时间范围，S，A分别是状态数和动作数。这是第一个在观测空间小于潜在状态空间的部分观测环境中不需要任何假设的高效算法。
在强化学习（RL）中，代理解决未知动态环境中的顺序决策问题，以最大化长期回报[46]。代理通过以状态相关的奖励和观察的形式接收其行为的反馈，从而与环境交互。RL中的一个关键挑战是探索：在缺乏自动探索特性（如系统的遍历性）的情况下，代理必须设计一个聪明的方案来从系统中探索不足的部分收集数据。在长期的工作中，针对完全可观测的环境，即在马尔可夫决策过程（MDP）框架下，提出了许多多项式时间算法[34，27，43，40，18]，对RL中的有效探索进行了广泛研究。例如，在表格MDP中，即具有有限数量的状态和动作的环境中，我们可以在没有任何系统动力学假设的情况下实现样本最优或最小最大遗憾[3，50]。与完全可观测环境相比，对部分可观测MDP（POMDP）的勘探知之甚少。通常，POMDP中的RL可能需要指数数量的样本（不简化结构假设）[35，31]。因此，重要的是考虑POMDP的自然子类，这些子类允许可处理的解决方案。先前的研究集中于一类特殊的POMDP，其中观察空间足够大，以至于单个观察可以提供关于潜在状态的足够信息[22，35，4，12，16，30]。然而，在机器人学、主题建模等领域有许多应用，其中观察空间小于潜在状态空间。这种“小观察空间”的设置至关重要，因为大多数先前的工作都不适用。我们的工作旨在为解决这一领域的一类问题提供首批成果之一。特别是，我们处理了受潜在变量或混合问题启发的POMDP子类。具体而言，我们考虑奖励混合MDP（RM MDP）。在RM MDP中，过渡核和初始状态分布被定义为标准MDP，而奖励函数在每集开始时从M奖励模型中随机选择（参见正式定义1）。RM MDP本身就很重要。例如，考虑一个动态网络系统中的用户交互模型，其中奖励模型因具有不同特征的用户而异[38，23]。最近的几篇论文[8、6、23、45、7]也考虑了类似的背景，最近的一篇，也是与我们的背景最直接相关的一篇[36]。即使对于M=2，RM-MDP设置也分担了一般POMDP的一些关键挑战。这是因为RM-MDP问题的最佳策略不仅应考虑当前状态，而且还应考虑先前观察的整个序列，因为某些先前事件可能与当前行动的奖励相关。在较小的观测空间设置中，不能应用[22，35，4，12，16，30]中的在先工作。[36]中的工作开发了一个算法框架，用于在这种小的观测环境中解决RM-MDP问题，但需要强有力的假设，否则算法将崩溃。我们将在下面对此进行更详细的讨论。事实上，迄今为止，没有任何工作能够解决RM-MDP问题，即使对于M=2，也没有重大的进一步假设。这正是我们在本文中要解决的问题。
主要结果和贡献我们关注在两个奖励混合MDP中学习接近最优策略的问题，即具有两个奖励模型M=2的RM MDP。据我们所知，在没有任何关于系统动力学的假设的情况下，即使对于M=2，先前的工作也没有研究RM MDP中RL的样本复杂性。特别地，我们提供了第一个多项式时间算法，该算法在探索O（poly（H−1）·S 2A2）发作。我们还表明Ω（S 2A2/2）事件数是必要的，因此我们的结果在S，A中是紧密的。这是在具有小观察空间且没有任何系统动力学假设的部分可观察域的子类中的第一个有效算法。在技术方面，我们必须克服一些在完全可观察的环境中不存在的新挑战。一个关键障碍与可识别性有关。在标准MDP中，来自单个状态动作对的单个观察的平均值足以获得状态动作的过渡和奖励模型的无偏估计。然而，在RM MDP中，相同的数量只会给出一个平均的奖励模型，其中平均值被用于奖励模型分配。然而，单独的平均奖励模型不足以获得取决于先前奖励序列的最优策略。我们的技术吸引了高阶矩中不确定性的想法，从学习结构化分布混合的算法中获得了灵感[19，9，26，15]。在这些问题中，有效学习的关键是利用高阶矩的信息。遵循这种精神，我们考虑在多个不同的国家行动中估计奖励的相关性。我们必须克服的一个核心挑战是，在有限水平MDP中，可能不可能以一致良好的精度估计所有高阶相关性。事实上，当某些状态动作对在同一事件中无法达到时，可能根本无法估计某些相关性。因此，我们不能简单地依赖现有的技术，这些技术需要对高阶矩矩阵中的所有元素进行良好的估计。因此，主要的技术挑战是，要证明一个接近最优的政策仍然可以从国家行为的不确定性和部分相关性中获得。因此，我们的技术贡献有两方面：（1）设计了一种有效的勘探算法，以估计每个相关性，达到一定的精度；（2）新的技术工具，以分析估计的高阶相关性中不同不确定性水平的误差。
