Safety reinforcement learning based on linear function approximation safe RL with linear function approximation translation 1

The paper ：Safe Reinforcement Learning with Linear Function Approximation
Download address ：http://proceedings.mlr.press/v139/amani21a/amani21a.pdf
meeting / year ：PMLR / 2021

Word Version download address （ Hard work ）：https://download.csdn.net/download/baishuiniyaonulia/85863332
The translation of this article belongs to semi manual , Please forgive me for any mistakes .

Abstract Abstract

In recent years , The security of reinforcement learning becomes more and more important . However , Existing solutions either cannot strictly avoid choosing unsafe actions , This may lead to catastrophic results for safety critical systems , Or it cannot provide a regrettable guarantee for the environment that needs to learn security constraints . In this paper , We solve these two problems by first modeling security as an unknown linear cost function of state and action , It must always be below a certain threshold . then , We propose an algorithm , be called SLUCB-QVI and RSLUCB-QVI, For finite level Markov decision processes with linear function approximation (MDP). We proved that SLUCB-QVI and RSLUCB-QVI Without violating security , Realized $\tilde{\mathcal{O}}\left(\kappa \sqrt{d^3{H}^{3}T}\right)$ regret , It almost matches the most advanced unsafe Algorithm , among $H$ Is the duration of each round ,$d$ Is the dimension of feature mapping ,$\kappa$ Is a constant representing a security constraint ,$T$ Is the total number of actions . We further propose numerical simulations to confirm our theoretical findings .

1. Introduce Introduction

Reinforcement learning (RL) It's a kind of research , That is, a subject tries to maximize its expected cumulative rewards through interaction with the unknown environment . In most classic RL In the algorithm, , The goal of an agent is to maximize long-term gain by exploring all possible actions . However , In many real-world systems , Free exploration of all behaviors, even unsafe games, can also be harmful actions that can lead to disastrous results . therefore ,RL The security of algorithm has become a serious problem , Limit RL The applicability of the algorithm in many real systems . for example , In the automatic driving vehicle , Explore those that avoid collisions and damage to cars 、 The policy of people and property is crucial . Conversion cost restrictions in medical applications and legal restrictions in financial management are other examples of safety critical applications . All of the above safety critical environments introduce a new challenge of balancing the goal of maximizing rewards with the limits of taking safety actions .

In order to solve this main problem , The learning algorithm needs to ensure that it does not violate certain security constraints . From the perspective of robber optimization , A linear robber problem is studied , In each round , Both need high probability to satisfy the linear cost constraint . For this question , They proposed a no regret algorithm with high probability that does not violate constraints . When the environment passes through the more challenging and complex unknown MDP When setting up modeling , To solve RL There has been a surge in research activities to explore security issues in . Many existing algorithms constrain Markov decision processes (CMDP) Yes RL Security Modeling , The classic MDP Extend to a range of settings that have additional constraints on the total expected cost . In order to solve CMDPs Safety requirements in , Different approaches have been proposed , As original - Dual strategy optimization 、 Constraint policy optimization and incentive constraint policy optimization . These algorithms either have no theoretical guarantee in batch offline settings , Or there is no guarantee of asymptotic convergence . In another study of online settings CMDP An algorithm of violating the sublinear limit of the constrained quantity is proposed in the work of . Besides , The security constraint considered in the above paper is defined by the cumulative expected cost below a certain threshold .

In this paper , We propose an upper trust realm (UCB)- Based on Algorithms - It is called safe linearity UCB Q/V iteration (SLUCB-QVI)- Focus on deterministic strategy choices , Respect the concept of stricter safety requirements , An action must be performed with a high probability at each time step . We also propose random SLUCB-QVI(RSLUCB-QVI), This is a safe algorithm , Focus on random strategy selection , Without violating any constraints . For both of these algorithms , We assume that the bottom MDP It has a linear structure , And proved that a regretful circle is equivalent to the unsafe part .

Our main technical contribution enables us to guarantee the sublinear regret constraint without violating the security constraint , Include ：1) Conservatively select actions from the subset of the correctly defined unknown security set ;2) Use careful algorithm design to ensure optimism in the face of security constraints , That is, the value function of our proposed algorithm is larger than the optimal value function . See the first 2、3、4 section .

Symbol Notation

We first introduce a set of symbols used throughout the paper . We use lowercase letters to represent scalars , Use lowercase bold letters to represent vectors , Use capital bold letters to represent the matrix .x The Euclidean norm of is written as $\Vert x{\Vert }_2$. We use it $x^{\top }$ Represents any column vector $x$ The transpose . For any vector $x$ and $y$, We use it $<x,y>$ To express their inner product . set up $x$ Positive definite $d\times d$ Matrix and $\nu \in {\mathbb{R}}^d$.$\nu$ be relative to $\mathbf{A}$ A weighted 2- The norm is defined as $\Vert \nu {\Vert }_2=\sqrt{{\nu }^{\top }\mathbf{A}\nu }$. For positive integers $n$,$[n]$ Express $\{1,2,...,n\}$. We use it $e_i$ To represent the $i$ Two standard basis vectors . Last , We ignore the large logarithm factor $O$ Symbols use standard $\tilde{\mathcal{O}}$ Symbol .

1.1. The problem is formulated Problem formulation

Finite horizon Markov decision process Finite-horizon Markov decision process

We consider a finite level Markov decision process (MDP), We consider a finite level Markov decision process (MDP), Expressed as $M=(\mathcal{S},\mathcal{A},H,\mathbb{P},r,c)$, among ,$\mathcal{S}$ It's a state set ,$\mathcal{A}$ It's an action set ,$H$ Is the length of each round （ The transverse ）,$\mathbb{P}=\{{\mathbb{P}}_h{\}}_{h=1}^H$ Is the transition probability ,$r=\{r_h{\}}_{h=1}^H$ It's a reward function ,$c=\{c_h{\}}_{c=1}^H$ It's a safe quantity . For each time step $h\in [H]$,${\mathbb{P}}_h(s^{\prime }|s,a)$ In state $s$ Make an action $a$ Transfer to the State $s^{\prime }$ Probability , also $r_h:\mathcal{S}\times \mathcal{A}\to [0,1]$, also $c_h:\mathcal{S}\times \mathcal{A}\to [0,1]$ Is a reward and constraint function . We consider the $S$ and $A$ Known learning problems , And the transition probability ${\mathbb{P}}_h$、 Reward $r_h$ And safety quantity $c_h$ It is unknown. , Must study online . Agents interact with unknown environments , The environment is described as $M$ In each round . In practice , In each round $k$ And time steps $h\in [H]$, The agent observes the State $s_h^k$, Make an action $a_h^k\in A$, Then observe a reward $r_h^k:=r_h(s_h^k,a_h^k)$, And a safety measure disturbed by noise $z_h^k=c_h(s_h^k,a_h^k)+{ϵ}_h^k$, among ${ϵ}_h^k$ It's a random noise .

Security constraints Safety Constraint

We assume that the security of the underlying system is crucial , The learning environment is constrained by the side that restricts the choice of action , In each round $k$ And time steps $h\in [H]$, In state $s_h^k$ when , The agent must choose a safe operation program , So that ：
$$c_h\left(s_h^k,a_h^k\right)\le \tau$$

among $\tau$ Is a known constant . therefore , We define the unknown set of security actions as :
$${\mathcal{A}}_h^{\text{safe}}(s):=\left\{a\in \mathcal{A}:c_h(s,a)\le \tau \right\},\forall (s,h)\in \mathcal{S}\times [H]$$

therefore , After observing the $k$ The state of the round $s_h^k$ And time steps $h\in [H]$ after , The action selection of the agent must probably belong to ${\mathcal{A}}_h^{safe}(s_h^k)$. As an example of heuristics , Consider a autonomous vehicle . One side , agent （ vehicle ） Get the reward from the first point to the second point as soon as possible . On the other hand , Driving behavior must be limited to compliance with traffic safety standards .

The goal is Goal

A secure deterministic strategy is a function $\pi :\mathcal{S}\times [H]\to \mathcal{A}$. such ,$\pi (s,h)\in {\mathcal{A}}_h^{safe}(s)$ It's a strategy $\pi$ It is suggested that the agent in the time step $h\in [H]$ And status $s\in \mathcal{S}$ Safety actions taken when . therefore , We go through :
$${\Pi }^{\text{safe}}:=\left\{\pi :\pi (s,h)\in {\mathcal{A}}_h^{\text{safe}}(s),\forall (s,h)\in \mathcal{S}\times [H]\right\}$$

For each $h\in [H]$, In a security policy $\pi \in {\prod }^{safe}$ The cumulative expected reward obtained under , Called value function $V_h^{\pi }：\mathcal{S}\to \mathbb{R}$, Is defined as :
$$V_h^{\pi }(s):=\mathbb{E}\left[\sum _{h^{\prime }=h}^H{r}_{h^{\prime }}\left(s_{h^{\prime }},\pi \left(s_{h^{\prime }},h^{\prime }\right)\right)|s_h=s\right]$$

Where expectations exceed the environment . We also define the state - Action value action $Q_h^{\pi }：\mathcal{S}\times {\mathcal{A}}_h^{safe}(.)\to \mathbb{R}$ For a security policy $\pi \in {\prod }^{safe}$ In time step $h\in [H]$ from :
$$Q_h^{\pi }(s,a):=\mathbb{E}\left[\sum _{h^{\prime }=h+1}^H{r}_{h^{\prime }}\left(s_{h^{\prime }},\pi \left(s_{h^{\prime }},h^{\prime }\right)\right)|s_h=s,a_h=a\right]$$

To simplify symbols , For any function f, We mean $[{\mathbb{P}}_{h}f](s,a):={\mathbb{E}}_{s^{\prime }\sim {\mathbb{P}}_h(.|s,a)}f(s^{\prime })$. Give Way ${\pi }_{\ast }$ Is the best security policy , such $V_h^{{\pi }_{\ast }}(s)=su{p}_{\pi \in {\prod }^{safe}}{V}_h^{\pi }(s)$ For all $(s,h)\in \mathcal{S}\times [H]$. therefore , For all $(s,h)\in \mathcal{S}\times [H]$ and $a\in {\mathcal{A}}_h^{safe}(s)$, Any security policy $\pi \in {\prod }^{safe}$ And optimal security policy Bellman The equation is ：
$$\begin{array}{rl}& Q_h^{\pi }(s,a)=r_h(s,a)+\left[{\mathbb{P}}_h{V}_{h+1}^{\pi }\right](s,a),\\ & V_h^{\pi }(s)=Q_h^{\pi }(s,\pi (s,h)),\end{array}$$$$\begin{array}{rl}& Q_h^{\ast }(s,a)=r_h(s,a)+\left[{\mathbb{P}}_h{V}_{h+1}^{\ast }\right](s,a).\\ & V_h^{\ast }(s)=\underset{a\in {\mathcal{A}}_h^{\text{safe }}(s)}{\max }{Q}_h^{\ast }(s,a),\end{array}$$

among $V_{H+1}^{\pi }(s)=V^{\ast }H+1(s)=0$. Please note that , In the classic without security constraints RL in , Behrman optimality equation means that there is at least one deterministic optimal strategy . When considering solving the Behrman equation of the optimal strategy , The existence of security constraints is equivalent to that without constraints but with different constraints MDP The solution of $(s,h)\in \mathcal{S}\times [H]$, namely ${\mathcal{A}}_h^{safe}(s)$

set up $K$ Is the total number of events ,$s_1^k$ For events $k\in [K]$ Initial state at the beginning ,${\pi }_k$ For agents in events $k\in [K]$ High probability security strategy selected during . Then define cumulative pseudo regret ：
$$R_K:=\sum _{k=1}^K{V}_1^{\ast }(s_1^k)-V_1^{{\pi }_k}(s_1^k)$$

The goal of an agent is to maintain $R_K$ As small as possible ($R_K/K\to 0$ With $K$ Bigger ), Instead of violating safety constraints in the process , namely ,${\pi }_k\in {\prod }^{safe}$ For all $k\in [K]$ There is a high probability .

Linear function approximation Linear Function Approximation

We are concerned with kernels with linear transfer 、 The reward and cost functions encapsulated in the following assumptions MDPs.

hypothesis 1 （ linear MDP） Assumption 1 (Linear MDP)

$M=(\mathcal{S},\mathcal{A},H,\mathbb{P},r,c)$ It has feature mapping $\varphi :\mathcal{S}\times OfLinesex\mathcal{M}\mathcal{D}\mathcal{P}\mathcal{A}\to {\mathbb{R}}^d$, If for any $h\in [H]$, There are unknown measures ${\mu }_h^{\ast }:={\left[{\mu }_h^{\ast (1)},\dots ,{\mu }_h^{\ast (d)}\right]}^{\top }$ exceed $\mathcal{S}$ And unknown vectors ${\theta }_h^{\ast }$, ${\gamma }_h^{\ast }\in {\mathbb{R}}^d$ bring ${\mathbb{P}}_h(.|s,a)=*{\mu }_h^{\ast }(.),\varphi (s,a)*,r_h(s,a)=*{\theta }_h^{\ast },\varphi (s,a)*$, and $c_h(s,a)=*{\gamma }_h^{\ast },\varphi (s,a)*$.

This assumption emphasizes linearity MDP The definition of , Among them, Markov transition model 、 Reward function and cost function in feature mapping $\varphi$ Is linear .

1.2. Related work Related works

Safety reinforcement learning and randomization strategy Safe RL with randomized policies

This paper studies constrained Markov decision-making processes focusing on unknown dynamic and stochastic strategies (CMDP) Formulated safety RL problem . (Efroni et al., 2020; Turchetta et al., 2020; Garcelon et al., 2020; Zheng and Ratliff, 2020; Ding et al., 2020a; Qiu et al., 2020; Ding et al., 2020b; Xu et al., 2020; Kalagarla et al., 2020). In the above paper , The goal is to find the optimal random strategy , Make the reward value function $V_r^{\pi }(s)$（ Expect total reward ） Maximize , At the same time, ensure the cost value function $V_c^{\pi }(s)$（ Expected total cost ） Do not exceed a certain threshold . This safety requirement is defined in a range , According to the randomization of environment and policy , Therefore, it is not as strict as the safety requirements considered in this article , And the safety requirements must be met in each time step , Will play an action . In addition to different problem formulas , The theoretical guarantee of these works is fundamentally different from that provided in this paper . Recent closely related work (Ding et al., 2020a) Study constraints at finite levels MDP Linear structure is realized by primitive strategy optimization algorithm in our paper $\tilde{\mathcal{O}}\left(d{H}^{2.5}\sqrt{T}\right)$ Regret and constraint violation , It can only be used to set limited action sets $\mathcal{A}$.(Efroni et al., 2020) The algorithm is optimized by linear programming and primal dual strategy , Get $\tilde{\mathcal{O}}(|\mathcal{S}|H^2\sqrt{|\mathcal{S}||\mathcal{A}|T})$ Regret and constraint violation . stay (Qiu et al., 2020) in , The author studied a case in $\tilde{\mathcal{O}}(|\mathcal{S}|H\sqrt{|\mathcal{A}|T})$ Regret and constraint violation constrained antagonistic stochastic shortest path problem .(Dingetal.,2020b) A primal dual algorithm for solving infinite horizon discount rate is proposed , The algorithm achieves the rate of optimality gap and constraint violation $\tilde{\mathcal{O}}(1/\sqrt{T})$ Global convergence of . The above work can only guarantee the limit of the number of violations of constraints , Our algorithm has never violated security constraints in the learning process .

In addition to the primal dual method , stay (Chow et al., 2018) in , Lyapunov function is also used to deal with constraints .(Yu et al., 2019) This paper presents a constrained strategy gradient algorithm with convergence guarantee . The above two works focus on solving with the known transition model and constraint function CMDPs Model , Without warranty of regret .

Safety reinforcement learning and gp And deterministic transfer models and strategies Safe RL with GPs and deterministic transition model and policies

In another job ,(Turchetta et al., 2016; Berkenkamp et al., 2017; Wachi et al., 2018; Wachi and Sui, 2020) Use Gaussian process, use deterministic transformation and / Or value function modeling dynamics , In order to be able to estimate constraints and ensure safe learning . Although some of these algorithms are approximately secure , But analyzing its convergence is still challenging , And lack of regret analysis .

2. Safe linearity UCB Of Q、V Value iteration Safe Linear UCB Q/V Iteration

In this section , We will introduce the algorithm 1 The secure linear upper confidence bound summarized in Q/V iteration (SLUCB-QVI), Then in the first 2 Its performance is described at a high level in section . First , We will describe the algorithm in the next chapter 1 And the following necessary assumptions and symbol sets used in its analysis .

hypothesis 2 （ Non empty safety set ） Assumption 2 (Non-empty safe sets)

For all $s\in \mathcal{S}$, There is a known safety action $a_0(s)$ bring $a_0(s)\in {\mathcal{A}}_h^{\text{safe}}(s)$ Known safety measures ${\tau }_h(s):=*\varphi \left(s,a_0(s)\right),{\gamma }_h^{\ast }*<\tau$ For all $h\in [H]$.

Understand safety actions $a_0(s)$ For solving the problem of safety linearity in this paper MDP Settings are necessary , This requires that constraints be met from the first round (1). This assumption is also true in many practical examples , The known safety actions may be the actions recommended by the company's current strategy , Or cost neutral action , There is not necessarily a high return , But its cost is far from reaching the threshold . It can relax and understand safety actions ${\tau }_h(s)$ Cost assumptions . under these circumstances , The agent starts with the time step $h$ Carry out a $a_0(s)$ round , In order to construct the gap interval time interval $\tau -{\tau }_h(s)$ Conservative estimator .$T_h(s)$ Choose in an adaptive way , In the appendix A.4 In, we show $\frac{16\log (K)}{(\tau -{\tau }_h(s){)}^2}\le T_h(s)\le \frac{64\log (K)}{(\tau -{\tau }_h(s){)}^2}$, stay $T_h(s)$ After wheel , The agent is calculating the estimated set of security policies （ later ） Depend on ${\tau }_h(s)$ Estimation （ Discussed later ）.

Symbol Notation

For any vector $\mathbf{x}\in {\mathbb{R}}^d$, Define normalized vector $\tilde{\mathbf{x}}:=\frac{\mathbf{x}}{\Vert \mathbf{x}{\Vert }_2}$. We will feature safety $\varphi \left(s,a_0(s)\right)$ The span of is defined as ${\mathcal{V}}_s=\mathrm{span}\left(\varphi \left(s,a_0(s)\right)\right):=\left\{\alpha \varphi \left(s,a_0(s)\right):\alpha \in \mathbb{R}\right\}$ and ${\mathcal{V}}_s$ The orthogonal complement of is ${\mathcal{V}}_s^{\perp }:=\left\{\mathbf{y}\in {\mathbb{R}}^d:*\mathbf{y},\mathbf{x}*=0,\forall \mathbf{x}\in {\mathcal{V}}_s\right\}$. For any $\mathbf{x}\in {\mathbb{R}}^d$, Write it down as ${\Phi }_0(s,\mathbf{x}):=left*\mathbf{x},\tilde{\varphi }\left(s,a_0(s)\right)*\tilde{\varphi }\left(s,a_0(s)\right)$ It's in ${\mathcal{V}}_s$ The projection on the , And through ${\Phi }_0^{\perp }(s,\mathbf{x}):=\mathbf{x}-{\Phi }_0(s,\mathbf{x})$ It is in the orthogonal subspace $\mathcal{V}$ The projection on the $s^{\perp }$. Besides , For convenience of marking , Make ${\varphi }_h^k:=\varphi \left(s_h^k,a_h^k\right)$.

2.1. overview Overview

From a high-level Perspective , Our algorithm is (Jin et al., 2020) Proposed LSVI-UCB Security version of . especially , Each round consists of two cycles on all time steps . First cycle （ The first 5-8 That's ok ） Number of updates ${\mathcal{A}}_h^k$, Estimated safety set sum $Q_h^k$, Action value function , That is, it is used to implement the upper confidence limit strategy $a_h^k=\arg {\max }_{a\in {\mathcal{A}}_h^k(s_h^k)}{Q}_h^k(s_h^k,a)$ In the second cycle （ The first 9-11 That's ok ）. SLUCB-QVI and LSVI-UCB The main difference between them is the required action $a_h^k$ Must always belong to an unknown security set ${\mathcal{A}}_h^{\text{safe }}(s_h^k)$. So , In every plot $k\in [K]$ in , In the first cycle （ The first 6 That's ok ） In the additional steps of , Agent computes a set ${\mathcal{A}}_h^k(s)$ For all $s\in \mathcal{S}$, We will prove that it is an unknown security set ${\mathcal{A}}_h^{\text{safe}}(s)$, therefore , From the second cycle （ The first 10 That's ok ） Choose the action $a_h^k$ A good candidate for . ${\mathcal{A}}_h^k(s)$ The construction of depends on the unknown parameters used in the definition of security constraints ${\gamma }_h^{\ast }$ ( See assumptions 1). Because the agent knows ${\tau }_h(s):=*\varphi \left(s,a_0(s)\right),gamm{a}_h^{\ast }*$（ See assumptions 2）, It can calculate $z_{h,s}^k:=*{\Phi }_0^{\perp }\left(s,{\varphi }_h^k\right),{\Phi }_0^{\perp }\left(s,{\gamma }_h^{\ast }\right)*+{ϵ}_h^k=z_h^k-\frac{{*{\varphi }_h^k,\tilde{\varphi }\left(s,a_0(s)\right)*}_1}{{\Vert \varphi \left(s,a_0(s)\right)\Vert }_2}{\tau }_h(s)$, namely $a_h^k$ Along the subspace ${\mathcal{V}}_s^{\perp }$ The cost incurred , It is associated with $\varphi \left(s,a_0(s)\right)$. therefore , Agents do not need to follow the normalized safety feature vector $\tilde{\varphi }\left(s,a_0(s)\right)$. contrary , It is only in ${\Phi }_0^{\perp }\left(s,{\gamma }_h^{\ast }\right)$ Establish the following confidence set around , It follows The orthogonal direction of the wave sign $\tilde{\varphi }\left(s,a_0(s)\right)$:
$${\mathcal{C}}_h^k(s):=\left\{\nu \in {\mathbb{R}}^d:{\Vert \nu -{\gamma }_{h,s}^k\Vert }_{{\mathbf{A}}_{h,s}^k}\le \beta \right\}$$

among ${\gamma }_{h,s}^k:={\left({\mathbf{A}}_{h,s}^k\right)}^{-1}{\mathbf{r}}_{h,s}^k$ yes ${\Phi }_0^{\perp }\left(s,{\gamma }_h^{\ast }\right)$ The regularized least squares estimator of is given by Gram Inverse calculation of matrix ${\mathbf{A}}_{h,s}^k:=\lambda \left(I-\tilde{\varphi }\left(s,a_0(s)\right){\tilde{\varphi }}^{\top }\left(s,a_0(s)\right)\right)+\sum _{j=1}^{k-1}{\Phi }_0^{\perp }\left(s,{\varphi }_h^j\right){\Phi }_0^{\perp ,\top }\left(s,{\varphi }_h^j\right)$ and $r_{h,s}^k:=\sum _{j=1}^{k-1}{z}_{h,s}^j{\Phi }_0^{\perp }\left(s,{\varphi }_h^j\right)$ . Explore factors β Will soon be in theorem 1 In the definition of , To ensure the event :

$${\mathcal{E}}_1:=\left\{{\Phi }_0^{\perp }\left(s,{\gamma }_h^{\ast }\right)\in {\mathcal{C}}_h^k(s),\forall (s,h,k)\in \mathcal{S}\times [H]\times [K]\right\}$$

namely ${\Phi }_0^{\perp }\left(s,{\gamma }_h^{\ast }\right)$ It belongs to the confidence set ${\mathcal{C}}_h^k(s)$, It is likely to be established . In implementation , We will β It is regarded as adjusting parameters . With events ${\mathcal{E}}_1$ On condition that , The agent is ready to calculate the real unknown security set ${\mathcal{A}}_h^{\text{safe}}$ The following internal approximation of all $s\in \mathcal{S}$ The safety of the ：
$$\begin{array}{rl}& {\mathcal{A}}_h^k(s)=\{a\in \mathcal{A}:\frac{*{\Phi }_0(s,\varphi (s,a)),\tilde{\varphi }\left(s,a_0(s)\right)*}{{\Vert \varphi \left(s,a_0(s)\right)\Vert }_2}{\tau }_h(s)\\ & +*{\gamma }_{h,s}^k,{\Phi }_0^{\perp }(s,\varphi (s,a))*+\beta {\Vert {\Phi }_0^{\perp }(s,\varphi (s,a))\Vert }_{{\left({\mathbf{A}}_{h,s}^k\right)}^{-1}}\le \tau \}\end{array}$$

Be careful $\frac{*{\Phi }_0(s,\varphi (s,a)),\tilde{\varphi }\left(s,a_0(s)\right)*}{{\Vert \varphi \left(s,a_0(s)\right)\Vert }_2}{\tau }_h(s)$ Is known in the state s Along the direction of $\tilde{\varphi }\left(s,a_0(s)\right)$ and $\underset{\nu \in {\mathcal{C}}_h^k(s)}{\max }*{\Phi }_0^{\perp }(s,\varphi (s,a)),\nu *=*{\gamma }_{h,s}^k,{\Phi }_0^{\perp }(s,\varphi (s,a))*+\beta {\Vert {\Phi }_0^{\perp }(s,\varphi (s,a))\Vert }_{{\left({\mathbf{A}}_{h,s}^k\right)}^{-1}}$ It is in orthogonal space ${\mathcal{V}}_s^{\perp }$ The maximum possible cost of . therefore ,$\frac{*{\Phi }_0(s,\varphi (s,a)),\tilde{\varphi }\left(s,a_0(s)\right)*}{{\Vert \varphi \left(s,a_0(s)\right)\Vert }_2}{\tau }_h(s)+*{\gamma }_{h,s}^k,{\Phi }_0^{\perp }(s,\varphi (s,a))*+\beta {\Vert {\Phi }_0^{\perp }(s,\varphi (s,a))\Vert }_{{\left({\mathbf{A}}_{h,s}^k\right)}^{-1}}$ Is the real unknown cost $*\varphi (s,a),{\gamma }_h^{\ast }*OfhighGeneralrateOnlimit$, It means ${\mathcal{A}}_h^k(s)\subset {\mathcal{A}}_h^{\text{safe}}(s)$.

proposal 1 Proposition 1

With (8) Medium ${\mathcal{E}}_1$ On condition that , For all $(s,h,k)\in \mathcal{S}\times [H]\times [K]$ , It thinks $*\varphi (s,a),{\gamma }_h^{\ast }*\le \tau ,\forall a\in {\mathcal{A}}_h^k(s)$.

therefore , With ${\mathcal{E}}_1$ On condition that , Decision making rules $a_h^k:=\arg {\max }_{a\in {\mathcal{A}}_h^k\left(s_h^k\right)}{Q}_h^k\left(s_h^k,a\right)$ Algorithm 1 Of the 10 Line indication $a_h^k$ Do not violate safety constraints . Be careful ${\mathcal{A}}_h^k(s)$ It's always non empty , Because as a hypothesis 2 Result , Safe action $a_0(s)$ Always in .${\mathcal{A}}_h^k(s)$ in .

Now that the estimated security set has been constructed ${\mathcal{A}}_h^k(s)$, We will describe how to calculate the action value function to be used $Q_h^k$ stay UCB Decision rules , Select actions in the second cycle of the algorithm $a_h^k$. MDP The linear structure of allows us to pass through the linear form $*{\mathbf{w}}_h^{\ast },\varphi (s,a)*$ A parameterized $Q_h^{\ast }(s,a)$ , among ${\mathbf{w}}_h^{\ast }:={\theta }_h^{\ast }+{\int }_{\mathcal{S}}{V}_{h+1}^{\ast }(s^{\prime })d\mu (s^{\prime })$. therefore , It is estimated that $Q_h^{\ast }(s,a)$ A natural idea of is to solve ${\mathbf{w}}_h^{\ast }$ The least squares problem . in fact , For all $(s,a)\in \mathcal{S}\times {\mathcal{A}}_h^k(.)$, Agent computing $Q_h^k(s,a)$ Defined as
$$Q_h^k(s,a)=\min \left\{*{\mathbf{w}}_h^k,\varphi (s,a)*+{\kappa }_h(s)\beta {\Vert \varphi (s,a)\Vert }_{{\left({\mathbf{A}}_h^k\right)}^{-1}},H\right\}$$

among ${\mathbf{w}}_h^k:={\left({\mathbf{A}}_h^k\right)}^{-1}{\mathbf{b}}_h^k$ yes ${\mathbf{w}}_h^{\ast }$ Regularized least squares estimator of , from Gram matrix Inverse calculation of ${\mathbf{A}}_h^k:=\lambda I+\sum _{j=1}^{k-1}{\varphi }_h^j{\varphi }_h^{j\top }$ and ${\mathbf{b}}_h^k:=\sum _{j=1}^{k-1}{\varphi }_h^j\left[r_h^j+{\max }_{a\in {\mathcal{A}}_{h+1}^k\left(s_{h+1}^j\right)}{Q}_{h+1}^k\left(s_{h+1}^j,a\right)\right]$. here ,${\kappa }_h(s)\beta {\Vert \varphi (s,a)\Vert }_{{\left({\mathbf{A}}_h^k\right)}^{-1}}$ Is the exploration reward, which is characterized by ： 1) β Encourage the right r and $\mathbb{P}$ To explore enough about the uncertainty of ; 2) ${\kappa }_h(s)>1$ Encourage the right c To explore enough about the uncertainty of . Although we use unsafe bandits and MDP (Abbasi-Yadkori et al., 2011) and (Jin et al., 2020) Standard analysis to define β, But quantify appropriately ${\kappa }_h(s)$ Is not safe LSVI-UCB comparison , The existence of security constraints gives SLUCB-QVI The main challenges of analysis , This is lemma 1 It says .

3. SLUCB-QVI It's a theoretical guarantee Theoretical guarantees of SLUCB-QVI

In this section , We will discuss the technical challenges that the existence of security constraints brings to our analysis , And for SLUCB-QVI Provide a regret boundary . Before that , We make the remaining necessary assumptions , Our proposed algorithm runs under these assumptions and achieves good regret bounds .

hypothesis 3 （ Sub Gaussian noise ） Assumption 3 (Subgaussian Noise)

For all $(h,k)\in [H]\times [K]$,${ϵ}_h^k$ Is a zero mean σ- Sub Gaussian noise A random variable .

hypothesis 4 （ bounded ） Assumption 4 (Boundedness)

No loss of generality ,${\Vert \varphi (s,a)\Vert }_2\le 1$ For all $(s,a)\in \mathcal{S}\times \mathcal{A}$ and $\max \left({\Vert {\mu }_h^{\ast }(\mathcal{S})\Vert }_2,{\Vert {\theta }_h^{\ast }\Vert }_2,{\Vert {\gamma }_h^{\ast }\Vert }_2\right)\le \sqrt{d}$ For all $h\in [H]$.

hypothesis 5 （ Star convex set ） Assumption 5 (Star convex sets)

For all $s\in \mathcal{S}$, aggregate $\mathcal{D}(s):=\{\varphi (s,a):a\in \mathcal{A}\}$ It's a star Focus on safety features $\varphi \left(s,a_0(s)\right)$ Convex set of , For all $\mathbf{x}\in \mathcal{D}(s)$ and $\alpha \in [0,1]$, $\alpha \mathbf{x}+(1-\alpha )\varphi \left(s,a_0(s)\right)\in \mathcal{D}(s)$.

hypothesis 3 and 4 It's linear MDP And the standards in the slot machine literature （Jin wait forsomeone ,2020;Pacchiano wait forsomeone ,2020;Amani wait forsomeone ,2019）. hypothesis 5 be necessary , To ensure that agents have the opportunity to explore a given security eigenvector $\varphi \left(s,a_0(s)\right)$ Surrounding feature space . for example , Consider a simple setup , among $\mathcal{S}=\{s_1\},\mathcal{A}=\{a_1,a_2\},H=1,{\mu }^{\ast }(s_1)=(1,1),{\theta }^{\ast }=(0,1)$, ${\gamma }^{\ast }=(0,1),\tau =2,a_0(s_1)=a_2$, and $\mathcal{D}(s_1)=\{\varphi (s_1,a_1),\varphi (s_1,a_2)\}=\{(0,1),(1,0)\}$, It is not a convex set . ad locum ,$a_1$ and $a_2$ Both actions are safe . The optimal security policy always uses $a_1$, It gives the highest reward . however , If $\mathcal{D}(s_1)$ Do not include connections $(1,0)$ and $(0,1)$ Entire line of , Then the intelligent experience will continue to play $a_2$ And will not be able to explore other security operations and determine the optimal strategy will always choose a1. Besides , It is worth mentioning that , aggregate $\mathcal{D}(s)$ Star convexity is safer than existing algorithms (Amani et al., 2019; Moradipari et al., 2019) The convexity assumption considered in the more moderate assumption ）.

Theorem 1 （SLUCB-QVI Regret value ） Theorem 1 (Regret of SLUCB-QVI)

Assuming 1、2、3、4 and 5 Next , There is an absolute constant $c_{\beta }>0$ So that for any fixed $\delta \in (0,0,5)$ , If we set $\beta :=\max \left(\sigma \sqrt{d\log \left(\frac{2+\frac{2T}{\lambda }}{\delta }\right)}+\sqrt{\lambda d},c_{\beta }dH\sqrt{\log \left(\frac{dT}{\delta }\right)}\right)$ and ${\kappa }_h(s):=\frac{2H}{\tau -{\tau }_h(s)}+1$, Then the probability is at least $1-2\delta$, It thinks $R_K\le 2H\sqrt{T\log \left(\frac{dT}{\delta }\right)}+(1+\kappa )\beta \sqrt{2dHT\log \left(1+\frac{K}{d\lambda }\right)}$, among $\kappa :={\max }_{(s,h)\in \mathcal{S}\times [H]}{\kappa }_h(s)$

here ,$T=KH$ Is the total number of actions played . We observe that the regret bound is the same order of magnitude as the most advanced unsafe Algorithm , for example LSVI-UCB (Jin et al., 2020), There is only one additional factor in the second term κ. The complete certificate is in the appendix A.3 Middle Report . In the next section , We give a sketch of the proof .

3.1. Theorem 1 Proof outline of

First , We state from (Abbasi-Yadkori et al., 2011; Jin et al., 2020) The following theorem borrowed .

Theorem 2 Theorem 2 (Thm. 2 in (Abbasi-Yadkori et al., 2011) and Lemma B.4 in (Jin et al., 2020)).

For any fixed strategy $\pi$, Definition $V_h^k(s):={\max }_{a\in {\mathcal{A}}_h^k(s,a)}{Q}_h^k(s,a)$ And events
$$\begin{array}{rl}& {\mathcal{E}}_2:=\{\left|*{\mathbf{w}}_h^k,\varphi (s,a)*-Q_h^{\pi }(s,a)+\left[{\mathbb{P}}_h\left(V_{h+1}^{\pi }-V_{h+1}^k\right)\right](s,a)\right|\\ & \le \beta \Vert \varphi (s,a){\Vert }_{{\left({\mathbf{A}}_h^k\right)}^{-1}},\forall (a,s,h,k)\in \mathcal{A}\times \mathcal{S}\times [H]\times [K]\}\end{array}$$
And recall （8） in E1 The definition of . that , Assuming 1、2、3、4 And Theorem 1 in β Under the definition of , There is an absolute constant $c_{\beta }>0$, So that for any fixed $\delta stay(0,0,5)$ in , The probability is at least $1-\delta$, event $\mathcal{E}:={\mathcal{E}}_2\bigcap {\mathcal{E}}_1$ Retain .

As our main technical contribution , In lemma 1 in , We proved that when ${\kappa }_h(s):=\frac{2H}{\tau -{\tau }_h(s)}+1$, Keep optimistic in the face of safety constraints , Guarantee $Q_h^{\ast }(s,a)\le Q_h^k(s,a)$ . Intuitively speaking , This is necessary , Because the algorithm 1 The first 10 The maximization of row is not in the whole ${\mathcal{A}}_h^{\text{safe}}\left(s_h^k\right)$, But it's just a subset . therefore , Need bigger ${\kappa }_h(s)$ value （ And unsafe algorithms LSVI-UCB Medium ${\kappa }_h(s)=1$ comparison ） Provide enough exploration for the algorithm , In order to ${\mathcal{A}}_h^k\left(s_h^k\right)$ Selected actions in - Usually enough - optimistic , namely , $Q_h^{\ast }(s,a)\le Q_h^k(s,a)$.

lemma 1 （ face SLUCB-QVI Optimistic attitude towards safety constraints ） Lemma 1 (Optimism in the face of safety constraint in SLUCB-QVI)

Make ${\kappa }_h(s):=\frac{2H}{\tau -{\tau }_h(s)}+1$ And assumptions 1,2,3 ,4,5 keep . then , With $\mathcal{E}$ On condition that , It thinks $V_h^{\ast }(s)\le V_h^k(s),\forall (s,h,k)\in \mathcal{S}\times [H]\times [K]$.

We're in the appendix A.2 Proof is reported in . As lemma 1 And Theorem 2 Events defined in ${\mathcal{E}}_2$ The direct conclusion of , We have :

$$Q_h^{\ast }(s,a)\le *{\mathbf{w}}_h^k,\varphi (s,a)*+\beta {\Vert \varphi (s,a)\Vert }_{{\left({\mathbf{A}}_h^k\right)}^{-1}}+\left[{\mathbb{P}}_h{V}_{h+1}^{\ast }-V_{h+1}^k\right](s,a)\le Q_h^k(s,a)$$ This is encapsulated in the following corollary .

inference 1 (UCB) Corollary 1 (UCB)

Give Way ${\kappa }_h(s):=\frac{2H}{\tau -{\tau }_h(s)}+1$ And let assumptions 1,2, 3,4,5 keep . then , With $\mathcal{E}$ On condition that , It thinks $Q_h^{\ast }(s,a)\le Q_h^k(s,a),\forall (a,s,h,k)\in \mathcal{A}\times \mathcal{S}\times [H]\times [K]$.

Using lemma 1 Proved SLUCB-QVI Of UCB After the nature , We are going to use classic unsafe LSVI-UCB (Jin et al., 2020) To complete the analysis and establish SLUCB-QVI The ultimate regret world .

4、5、6

Safety reinforcement learning based on linear function approximation Safe RL with Linear Function Approximation translate 2 —— https://blog.csdn.net/baishuiniyaonulia/article/details/125572881