我们提出了一种非平稳核土匪的算法，该算法不需要事先了解非平稳性程度。该算法遵循通过解决平衡探索和剥削的优化问题获得的随机策略。当检测到奖励函数的更改时，它可以通过重新启动来适应非平稳性。我们的算法比以前在非平稳内核强盗设置上的工作更加动态遗憾。此外，当通过使用线性内核应用于非平稳线性匪徒设置时，我们的算法几乎是最小的最佳选择，可以解决非平稳的线性匪徒文献中的空旷问题。我们将算法扩展到使用神经网络，以动态调整特征映射到观察到的数据。我们证明了使用神经切线内核理论的延伸的动态遗憾。我们从经验上证明，我们的算法和扩展可以适应不同程度的非平稳性。

汤普森采样（TS）是解决上下文多武装强盗问题最有效的算法之一。在本文中，我们提出了一种新的算法，称为神经汤普森采样，这适应了深度神经网络，用于勘探和剥削。在我们的算法的核心是一种新的奖励的后分布，其平均值是神经网络近似器，并且其方差建立在相应神经网络的神经切线特征上。我们证明，如果底层奖励函数是有界的，则可以保证所提出的算法来实现$ \ mathcal {o}（t ^ {1/2}）$的累积遗憾，它与其他上下文强盗算法的遗憾匹配总轮数量$ t $。各种数据集中其他基准强盗算法的实验比较证实了我们的理论。

我们研究了具有线性函数近似增强学习中的随机最短路径（SSP）问题，其中过渡内核表示为未知模型的线性混合物。我们将此类别的SSP问题称为线性混合物SSP。我们提出了一种具有Hoeffding-type置信度的新型算法，用于学习线性混合物SSP，可以获得$ \ tilde {\ Mathcal {o}}}}（d B _ {\ star}^{1.5} \ sqrt {k/c_ {k/c_ {k/c_ {k/c_ { \ min}}）$遗憾。这里$ k $是情节的数量，$ d $是混合模型中功能映射的维度，$ b _ {\ star} $限制了最佳策略的预期累积成本，$ c _ {\ min}>> 0 $是成本函数的下限。当$ c _ {\ min} = 0 $和$ \ tilde {\ mathcal {o}}}（k^{2/3}）$遗憾时，我们的算法也适用于情况。据我们所知，这是第一个具有sublrinear遗憾保证线性混合物SSP的算法。此外，我们设计了精致的伯恩斯坦型信心集并提出了改进的算法，该算法可实现$ \ tilde {\ Mathcal {o}}}（d b _ {\ star} \ sqrt {k/c/c/c {k/c _ {\ min}}） $遗憾。为了补充遗憾的上限，我们还证明了$ \ omega（db _ {\ star} \ sqrt {k}）$的下限。因此，我们的改进算法将下限匹配到$ 1/\ sqrt {c _ {\ min}} $ factor和poly-logarithmic因素，从而实现了近乎最佳的遗憾保证。

我们考虑通过有限的地平线$ t $控制线性二次调节器（LQR）系统的问题，以固定和已知的成本矩阵$ q，r $但未知和非静止动力$ \ {a_t，b_t \} $。动态矩阵的序列可以是任意的，但总体变化，V_T $，假设为$ O（t）$和控制器未知。在假设所有$ $ $的稳定序列，但潜在的子最优控制器中，我们介绍了一种实现$ \ tilde {\ mathcal {o}} \ left的最佳动态遗憾的算法（v_t ^ { 2/5} t ^ {3/5} \右）$。通过分词恒定动态，我们的算法实现了$ \ tilde {\ mathcal {o}}（\ sqrt {st}）$的最佳遗憾，其中$ s $是交换机的数量。我们的算法的关键是一种自适应的非平稳性检测策略，它在最近开发的用于上下文多武装匪徒问题的方法中构建。我们还争辩说，不适应忘记（例如，重新启动或使用静态窗口大小的滑动窗口学习）可能对LQR问题的后悔最佳，即使窗口大小以$ V_T $的知识最佳地调整。我们算法分析中的主要技术挑战是证明普通的最小二乘（OLS）估计器在待估计的参数是非静止的情况下具有小的偏差。我们的分析还突出了推动遗憾的关键主题是LQR问题在于LQR问题是具有线性反馈和局部二次成本的强盗问题。这个主题比LQR问题本身更普及，因此我们相信我们的结果应该找到更广泛的应用。

我们考虑使用图形结构数据定义的奖励函数的强盗优化问题。这个问题在分子设计和药物发现中具有重要的应用，在图形排列中，奖励自然不变。这种设置的主要挑战是扩展到大型域，以及带有许多节点的图形。我们通过将置换不变性嵌入我们的模型来解决这些挑战。特别是，我们表明图形神经网络（GNN）可用于估计奖励函数，假设它位于置换不变的加性核的再现内核希尔伯特空间。通过在此类内核与图形神经切线内核（GNTK）之间建立新的联系，我们介绍了第一个GNN信心绑定，并使用它来设计一个带有sublinear遗憾的相位脱口算法。我们的遗憾约束取决于GNTK的最大信息增益，我们也为此提供了界限。虽然奖励功能取决于所有$ n $节点功能，但我们的保证与图形节点$ n $的数量无关。从经验上讲，我们的方法在图形结构域上表现出竞争性能，并表现得很好。

脱机策略学习（OPL）利用现有数据收集了策略优化的先验，而无需任何活动探索。尽管存在普遍性和近期对此问题的兴趣，但其函数近似设置中的理论和算法基础仍然持续开发。在本文中，我们考虑了在具有神经网络的离线上下文匪徒中的分布换档，优化和泛化轴上的这个问题。特别是，我们提出了一种可从线有效的离线情境匪徒，具有神经网络函数近似，不需要对奖励的任何功能假设。我们表明，我们的方法在较温和的情况下通过不良语境提供了比现有的OPL工作的分支变换。值得注意的是，与任何其他OPL方法不同，我们的方法使用随机梯度血统以在线方式从脱机数据中学习，允许我们利用在线学习的优势进入离线设置。此外，我们表明我们的方法更加计算效率，并且更好地依赖于神经网络的有效维度而不是在线对应物。最后，我们展示了我们在一系列合成和现实世界OPL问题中的方法的实证效果。

Many applications require optimizing an unknown, noisy function that is expensive to evaluate. We formalize this task as a multiarmed bandit problem, where the payoff function is either sampled from a Gaussian process (GP) or has low RKHS norm. We resolve the important open problem of deriving regret bounds for this setting, which imply novel convergence rates for GP optimization. We analyze GP-UCB, an intuitive upper-confidence based algorithm, and bound its cumulative regret in terms of maximal information gain, establishing a novel connection between GP optimization and experimental design. Moreover, by bounding the latter in terms of operator spectra, we obtain explicit sublinear regret bounds for many commonly used covariance functions. In some important cases, our bounds have surprisingly weak dependence on the dimensionality. In our experiments on real sensor data, GP-UCB compares favorably with other heuristical GP optimization approaches.

我们研究了一种强化学习理论（RL），其中学习者在情节结束时仅收到一次二进制反馈。尽管这是理论上的极端测试案例，但它也可以说是实际应用程序的代表性，而不是在RL实践中，学习者在每个时间步骤中都会收到反馈。的确，在许多实际应用的应用程序中，例如自动驾驶汽车和机器人技术，更容易评估学习者的完整轨迹要么是“好”还是“坏”，但是更难在每个方面提供奖励信号步。为了证明在这种更具挑战性的环境中学习是可能的，我们研究了轨迹标签由未知参数模型生成的情况，并提供了一种统计和计算上有效的算法，从而实现了sublinear遗憾。

本文以非线性功能近似研究基于模型的匪徒和增强学​​习（RL）。我们建议研究与近似局部最大值的收敛性，因为我们表明，即使对于具有确定性奖励的一层神经网络匪徒，全球收敛在统计上也很棘手。对于非线性匪徒和RL，本文介绍了一种基于模型的算法，即具有在线模型学习者（小提琴）的虚拟攀登，该算法可证明其收敛到局部最大值，其样品复杂性仅取决于模型类的顺序Rademacher复杂性。我们的结果意味着在几种具体设置（例如有限或稀疏模型类别的线性匪徒）和两层神经净匪内的新型全球或本地遗憾界限。一个关键的算法洞察力是，即使对于两层神经净模型类别，乐观也可能导致过度探索。另一方面，为了收敛到本地最大值，如果模型还可以合理地预测真实返回的梯度和Hessian的大小，则足以最大化虚拟返回。

我们研究了批量线性上下文匪徒的最佳批量遗憾权衡。对于任何批次数$ M $，操作次数$ k $，时间范围$ t $和维度$ d $，我们提供了一种算法，并证明了其遗憾的保证，这是由于技术原因，具有两阶段表达作为时间的时间$ t $ grose。我们还证明了一个令人奇迹的定理，令人惊讶地显示了在问题参数的“问题参数”中的两相遗憾（最高〜对数因子）的最优性，因此建立了确切的批量后悔权衡。与最近的工作\ citep {ruan2020linear}相比，这表明$ m = o（\ log \ log t）$批次实现无需批处理限制的渐近最佳遗憾的渐近最佳遗憾，我们的算法更简单，更易于实际实现。此外，我们的算法实现了所有$ t \ geq d $的最佳遗憾，而\ citep {ruan2020linear}要求$ t $大于$ d $的不切实际的大多项式。沿着我们的分析，我们还证明了一种新的矩阵集中不平等，依赖于他们的动态上限，这是我们的知识，这是其文学中的第一个和独立兴趣。

我们在非静止线性（AKA低级别）马尔可夫决策过程（MDP）中研究了集中加强学习，即奖励和转换内核都是关于给定特征映射的线性，并且被允许缓慢或突然演变时间。对于此问题设置，我们提出了一种基于加权最小二乘值的乐观模型算法的Opt-WLSVI，其使用指数权重来平滑地忘记过去远远的数据。我们表明我们的算法在每次竞争最佳政策时，实现了由$ \ widetilde {\ mathcal {o}}的上部界限的遗憾（d ^ {5/4} h ^ 2 \ delta ^ {1 / 4} k ^ {3/4}）$何地在$ d $是特征空间的尺寸，$ h $是规划地平线，$ k $是剧集的数量和$ \ delta $是一个合适的衡量标准MDP的非固定性。此外，我们指出了在忘记以前作品的非静止线性匪徒环境中忘记策略的技术差距，并提出了修复其遗憾分析。

我们介绍了一个多臂强盗模型，其中奖励是多个随机变量的总和，每个动作只会改变其中的分布。每次动作之后，代理都会观察所有变量的实现。该模型是由营销活动和推荐系统激励的，在该系统中，变量代表单个客户的结果，例如点击。我们提出了UCB风格的算法，以估计基线上的动作的提升。我们研究了问题的多种变体，包括何时未知基线和受影响的变量，并证明所有这些变量均具有sublrinear后悔界限。我们还提供了较低的界限，以证明我们的建模假设的必要性是合理的。关于合成和现实世界数据集的实验显示了估计不使用这种结构的策略的振奋方法的好处。

强化学习理论集中在两个基本问题上：实现低遗憾，并确定$ \ epsilon $ - 最佳政策。虽然简单的减少允许人们应用低温算法来获得$ \ epsilon $ - 最佳政策并达到最坏的最佳速率，但尚不清楚低regret算法是否可以获得实例 - 最佳率的策略识别率。我们表明这是不可能的 - 在遗憾和确定$ \ epsilon $ - 最佳政策之间以最佳的利率确定了基本的权衡。由于我们的负面发现，我们提出了针对PAC表格增强学习实例依赖性样本复杂性的新量度，该方法明确说明了基础MDP中可达到的国家访问分布。然后，我们提出和分析一种基于计划的新型算法，该算法达到了这种样本的复杂性 - 产生的复杂性会随着次要差距和状态的“可达到性”而缩放。我们显示我们的算法几乎是最小的最佳选择，并且在一些示例中，我们实例依赖性样品复杂性比最差案例界限可显着改善。

我们在嵌套政策类别的存在下研究匪徒场景中的模型选择问题，目的是获得同时的对抗和随机性（“两全其美”）高概率的遗憾保证。我们的方法要求每个基础学习者都有一个候选人的遗憾约束，可能会或可能不会举行，而我们的元算法按照一定时间表来扮演每个基础学习者，该时间表使基础学习者的候选人后悔的界限保持平衡，直到被发现违反他们的保证为止。我们开发了专门设计的仔细的错误指定测试，以将上述模型选择标准与利用环境的（潜在良性）性质的能力相结合。我们在对抗环境中恢复畜栏算法的模型选择保证，但是在实现高概率后悔界限的附加益处，特别是在嵌套对抗性线性斑块的情况下。更重要的是，我们的模型选择结果也同时在差距假设​​下的随机环境中同时保持。这些是在（线性）匪徒场景中执行模型选择时，可以达到世界上最好的（随机和对抗性）保证的第一个理论结果。

我们解决了有限地平线的模型选择的问题，用于转换内核$ P ^ * $属于一个型号$ \ mathcal {p} ^ * $的offultic公制熵。在模型选择框架中，而不是$ \ mathcal {p} ^ * $，我们被给予了$ m $嵌套的转换内核rested interned内核$ \ cp_1 \ subset \ cp_2 \ subset \ ldots \ subset \ cp_m $。我们提出并分析了一种新颖的算法，即\ EMPH {自适应增强学习（常规）}（\ texttt {arl-gen}），它适应真正的转换内核$ p ^ * $谎言的最小这些家庭。 \ texttt {arl-gen}使用具有价值目标回归的上置信度强化学习（\ texttt {Ucrl}）算法作为Blackbox，并在每个时代的开头放置模型选择模块。在模型类上的温和可分离性假设下，我们显示\ texttt {arl-gen}获得$ \ tilde {\ mathcal {o}}的后悔（d _ {\ mathcal {e}} ^ * h ^ 2 + \ sqrt {d _ {\ mathcal {e}} ^ * \ mathbb {m} ^ * h ^ 2 t}）$，具有高概率，其中$ h $是地平线长度，$ t $是步骤总数， $ d _ {\ mathcal {e}} ^ * $是ecured维度和$ \ mathbb {m} ^ * $是与$ \ mathcal {p} ^ * $相对应的度量熵。请注意，这一遗憾缩放匹配Oracle的Oracle，它提前了解$ \ mathcal {p} ^ * $。我们表明，对于\ texttt {arl-gen}的模型选择成本是一个附加术语，遗憾是对$ t $的弱点。随后，我们删除可分离假设，并考虑线性混合MDP的设置，其中转换内核$ P ^ * $具有线性函数近似。通过这种低等级结构，我们提出了新颖的自适应算法，用于模型选择，并获得（令人令人令）与Oracle的遗憾相同，具有真正的模型类。

本文调查了非静止线性匪徒的问题，其中未知的回归参数随着时间的推移而发展。现有的研究开发了各种算法并显示他们享受$ \ widetilde {\ mathcal {p_t ^ {1/3}）$动态遗憾，其中$ t $是时间范围和$ p_t $是测量演化未知参数的波动的路径长度。在本文中，我们发现一个严肃的技术缺陷使其结果未接地，然后呈现一个FIX，它给出$ \ WidTilde {\ Mathcal {o}}（t ^ {3/4} p_t ^ {1/4} ）$动态遗憾而不修改原始算法。此外，我们证明了代替使用复杂的机制，例如滑动窗口或加权罚款，简单的重启策略足以实现相同的遗憾保证。具体而言，我们设计了UCB型算法来平衡利用和探索，并定期重新启动它以处理未知参数的漂移。我们的方法享有$ \ widetilde {\ mathcal {o}}（t ^ {3/4} p_t ^ {1/4}）$动态遗憾。请注意，为了实现这一界限，该算法需要Oracle知识路径长度$ P_T $。将强盗带式机制组合通过将我们的算法视为基础学习者，我们可以通过无参数方式实现相同的遗憾。实证研究还验证了我们方法的有效性。

We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base algorithm abstraction that can work with general classes of base algorithms and different type of adversarial meta-algorithms. Our methods rely on a novel and generic smoothing transformation for bandit algorithms that permits us to obtain optimal $O(\sqrt{T})$ model selection guarantees for stochastic contextual bandit problems as long as the optimal base algorithm satisfies a high probability regret guarantee. We show through a lower bound that even when one of the base algorithms has $O(\log T)$ regret, in general it is impossible to get better than $\Omega(\sqrt{T})$ regret in model selection, even asymptotically. Using our techniques, we address model selection in a variety of problems such as misspecified linear contextual bandits, linear bandit with unknown dimension and reinforcement learning with unknown feature maps. Our algorithm requires the knowledge of the optimal base regret to adjust the meta-algorithm learning rate. We show that without such prior knowledge any meta-algorithm can suffer a regret larger than the optimal base regret.

We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic $Q$-Learning (VO$Q$L), based on $Q$-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VO$Q$L achieves $\tilde{O}(d\sqrt{HT}+d^6H^{5})$ regret over $T$ episodes for a horizon $H$ MDP under ($d$-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

获取一阶遗憾界限 - 遗憾的界限不是作为最坏情况，但有一些衡量给定实例的最佳政策的性能 - 是连续决策的核心问题。虽然这种界限存在于许多设置中，但它们在具有大状态空间的钢筋学习中被证明是难以捉摸的。在这项工作中，我们解决了这个差距，并表明可以将遗憾的缩放作为$ \ mathcal {o}（\ sqrt {v_1 ^ \ star}）$中的钢筋学习，即用大状态空间，即线性MDP设置。这里$ v_1 ^ \ star $是最佳政策的价值，$ k $是剧集的数量。我们证明基于最小二乘估计的现有技术不足以获得该结果，而是基于强大的Catoni平均估计器制定一种新的稳健自归一化浓度，其可能具有独立兴趣。

我们考虑在具有非线性函数近似的两名玩家零和马尔可夫游戏中学习NASH平衡，其中动作值函数通过繁殖内核Hilbert Space（RKHS）中的函数近似。关键挑战是如何在高维函数空间中进行探索。我们提出了一种新颖的在线学习算法，以最大程度地减少双重性差距来找到NASH平衡。我们算法的核心是基于不确定性的乐观原理得出的上和下置信度界限。我们证明，在非常温和的假设上，我们的算法能够获得$ O（\ sqrt {t}）$遗憾，并在对奖励功能和马尔可夫游戏的基本动态下进行多项式计算复杂性。我们还提出了我们的算法的几个扩展，包括具有伯恩斯坦型奖励的算法，可以实现更严格的遗憾，以及用于模型错误指定的另一种算法，可以应用于神经功能近似。