We study reinforcement learning with linear function approximation, unknown
transition, and adversarial losses in the bandit feedback setting.
Specifically, we focus on linear mixture MDPs whose transition kernel is a
linear mixture model. We propose a new algorithm that attains an
$\widetilde{O}(d\sqrt{HS^3K} + \sqrt{HSAK})$ regret with high probability,
where $d$ is the dimension of feature mappings, $S$ is the size of state space,
$A$ is the size of action space, $H$ is the episode length and $K$ is the
number of episodes. Our result strictly improves the previous best-known
$\widetilde{O}(dS^2 \sqrt{K} + \sqrt{HSAK})$ result in Zhao et al. (2023a)
since $H \leq S$ holds by the layered MDP structure. Our advancements are
primarily attributed to (i) a new least square estimator for the transition
parameter that leverages the visit information of all states, as opposed to
only one state in prior work, and (ii) a new self-normalized concentration
tailored specifically to handle non-independent noises, originally proposed in
the dynamic assortment area and firstly applied in reinforcement learning to
handle correlations between different states.

我们研究了采用线性函数逼近、未知转移和对抗性损失函数的强化学习算法在强化学习环境下。

改进的对抗性线性混合马尔可夫决策过程算法：带有赌博反馈和未知状态转移

Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit  Feedback and Unknown Transition

We consider a weakly supervised learning scenario where the supervision
signal is generated by a transition function $\sigma$ of labels associated with
multiple input instances. We formulate this problem as \emph{multi-instance
Partial Label Learning (multi-instance PLL)}, which is an extension to the
standard PLL problem. Our problem is met in different fields, including latent
structural learning and neuro-symbolic integration. Despite the existence of
many learning techniques, limited theoretical analysis has been dedicated to
this problem. In this paper, we provide the first theoretical study of
multi-instance PLL with possibly an unknown transition $\sigma$. Our main
contributions are as follows. Firstly, we propose a necessary and sufficient
condition for the learnability of the problem. This condition non-trivially
generalizes and relaxes the existing small ambiguity degree in the PLL
literature, since we allow the transition to be deterministic. Secondly, we
derive Rademacher-style error bounds based on a top-$k$ surrogate loss that is
widely used in the neuro-symbolic literature. Furthermore, we conclude with
empirical experiments for learning under unknown transitions. The empirical
results align with our theoretical findings; however, they also expose the
issue of scalability in the weak supervision literature.

本文针对监督信号由多输入实例上的标签的转移函数 σ 生成的弱监督学习方案，提出了多实例偏标签学习（multi-instance PLL）问题，并给出了对于可能的未知转移 σ 的第一理论分析。通过使用一种在神经符号学中广泛使用的顶部 - k 替代损失，我们推导了基于 Rademacher 的错误界限，并进行了实证实验。

利用多实例弱监督学习潜在模型

On Learning Latent Models with Multi-Instance Weak Supervision

We make significant progress toward the stochastic shortest path problem with
adversarial costs and unknown transition. Specifically, we develop algorithms
that achieve $\widetilde{O}(\sqrt{S^2ADT_\star K})$ regret for the
full-information setting and $\widetilde{O}(\sqrt{S^3A^2DT_\star K})$ regret
for the bandit feedback setting, where $D$ is the diameter, $T_\star$ is the
expected hitting time of the optimal policy, $S$ is the number of states, $A$
is the number of actions, and $K$ is the number of episodes. Our work strictly
improves (Rosenberg and Mansour, 2020) in the full information setting, extends
(Chen et al., 2020) from known transition to unknown transition, and is also
the first to consider the most challenging combination: bandit feedback with
adversarial costs and unknown transition. To remedy the gap between our upper
bounds and the current best lower bounds constructed via a stochastically
oblivious adversary, we also propose algorithms with near-optimal regret for
this special case.

本文主要研究随机最短路径问题中的对手成本和未知转移，并提出了一种新的算法，可以在有限的次数内找到最优解，此外，我们还提出了一种新的算法，可以在特定情景下近似达到最优解。