我们研究了一种强化学习（RL）理论，其中学习者在一集结束时只接受一次二元反馈。虽然这是一个极端的理论测试案例，但它也可以说比RL实践中的传统要求更能代表真实世界的应用，即学习者在每一个时间步都能收到反馈。事实上，在强化学习的许多现实应用中，如自动驾驶汽车和机器人技术，评估学习者的完整轨迹是好的还是坏的更容易，但在每一步都很难提供奖励信号。为了证明在这种更具挑战性的环境中学习是可能的，我们研究了由未知参数模型生成轨迹标签的情况，并提供了一种统计和计算上有效的算法，实现了次线性遗憾。
强化学习（RL）范式涉及学习主体在多个时间步长上与未知动态环境交互。学习者在每一步之后都会收到一个奖励信号，随着时间的推移，学习者会用这个信号来提高自己的表现。最近，RL的这一公式在经验上取得了重大成功[24，23，33，32]。尽管这一经验上的成功令人鼓舞，但随着RL开始解决更广泛的后果性现实问题，如自动驾驶汽车、供应链和医疗保健，一系列新的挑战出现了。其中最重要的是，在许多现实世界中，缺乏与每个状态-动作对相关联的明确的奖励信号。例如，考虑一个机器人操作任务，其中机器人必须折叠一堆衣服。目前尚不清楚如何设计一个有用的奖励信号来帮助机器人学习完成这项任务。然而，很容易检查任务是否成功完成（即衣服是否正确折叠），并在该集结束时提供反馈。这是一个经典的挑战，但在RL的理论处理中经常被忽视。为了应对这一挑战，我们引入了一个RL框架，该框架避免了在每一步都需要马尔可夫奖励信号，并仅基于其在一集中的完整轨迹向学习者提供二进制反馈。在我们的框架中，学习者在每一集中与环境互动固定数量的时间步长（H），以产生轨迹（τ），该轨迹是在这些回合中访问的所有状态和采取的行动的集合。在该集的结尾，二元奖励yτ∈ ｛0，1｝从未知分布Q（·|τ）中提取并交给学习者。该方案持续N集，学习者的目标是最大化预期的二元“成功”次数。解决文献中缺乏奖励函数的一种方法是反向强化学习[25]，它使用良好轨迹的演示来学习奖励函数。然而，当好的演示成本过高或难以获得时，这种方法很难使用。另一个密切相关的工作领域研究了带有偏好反馈的强化学习[2，15，3，5，37，26，38]。我们的框架为学习者提供的反馈形式甚至比这一工作中研究的反馈形式更弱。我们不在轨迹之间提供偏好，只在最后告知学习者任务是否成功完成
为了研究在这种极度有限的反馈下是否有可能学习，我们研究了条件奖励（yτ）从未知逻辑模型中得出的情况（见假设2.1）。在此假设下，我们证明学习是可能的，我们提供了一种基于乐观主义的算法，实现了次线性遗憾（见定理3.2）。从技术上讲，我们的理论利用了Russac等人[31]的最新结果，在线估计基础逻辑模型的参数，并将其与UCBVI算法[4]相结合，以获得遗憾边界。在可探索性假设下，我们还证明了我们的算法在计算上是有效的，并且我们提供了一种动态规划算法来求解每一集的乐观策略。我们注意到，Efroni等人[11]研究了一个与我们类似的问题，即奖励仅在一集结束时显示，但他们假设存在一个确定与每个状态动作对相关的奖励的潜在线性模型，并且向学习者显示的奖励是加有随机噪声的状态动作对上的奖励之和。这种假设确保了奖励函数是马尔可夫的，并允许他们使用在线线性匪徒算法[1]来直接估计潜在的奖励函数。这在我们的设置中是不可能的，因为我们不假设存在潜在的马尔可夫奖励函数。Cohen等人[6]提供了一种算法，即使在对抗性地选择噪声时，该算法也能在这种情况下学习。Efroni等人[11]提出的一个开放问题是，当奖励从未知广义线性模型（GLM）中提取时，找到一种在这种强化学习环境中学习的算法，每集一次反馈。在本文中，我们考虑一个特定的GLM——逻辑模型。本文的其余部分组织如下。在第2节中，我们介绍了符号并描述了我们的设置。在第3节中，我们介绍了我们的算法和主要结果。在可探索性假设下，我们证明了我们的算法在计算上是有效的（见附录E）。第4节指出了其他相关工作，我们在第5节中进行了讨论。其他技术细节、证明和实验将推迟到附录中。
