Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism

tags: RL Group meeting

2022/12/27

Abstract

• The new framework is centered around a weak version of the concentrability coefficient that measures the deviation of the behavior policy from the expert policy alone.
• We consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL.

Outline

1. Introduction

2. Background and problem formulation

3. A warm-up: LCB in multi-armed bandits

4. LCB in contextual bandits

5. LCB in Markov decision processes

6. Proof techniques and conjecture

7. Discussion

1. Introduction

• The online paradigm falls short of leveraging previously-collected datasets.
• The key component of offline RL is a pre-collected dataset from an unknown stochastic environment.

• Expert data : Algorithm achieves the minimal sub-optimality of 1/N in episodic Markov decision processes (MDPs).
• Uniform coverage data : Algorithms developed for this regime are demonstrated to achieve a 1/
  $\sqrt{N}$ sub-optimality competing with the optimal policy.

Motivating questions

Q1. Can we propose an offline RL framework that accommodates the entire data composition range?

• We characterize the data composition in terms of the ratio between the state-action occupancy density of an optimal policy
  $d^{\ast }(s,a)$ and that of the data distribution
  $\mu (s,a)$.
  • $C^{\ast }$ is the smallest constant satisfies
    $d^{\ast }(s,a)$/
    $\mu (s,a)$ ≤
    $C^{\ast }$
• We point out that existing works on offline RL either do not specify the dependency of sub-optimality on data coverage or do not have a batch data coverage assumption that accommodates the entire data spectrum.
• Unifying offline RL and imitation learning via a single algorithm is thus beneficial.

Q2. Can we design algorithms that can achieve minimal suboptimality when facing different dataset compositions without knowing

$C^{\ast }$ beforehand?

• We analyze a pessimistic variant of a value-based method.
• We first form a lower confidence bound (LCB) for the value function of a policy using the batch data
• Then, seek to find a policy that maximizes the LCB
  

2 Background and problem formulation

Markov decision processes

• $M=(S,A,P,R,\rho ,\gamma )$
• $d^{\pi }(s,a):=(1-\gamma ){\mathrm{\Sigma }}_{t=0}^{\infty }{\gamma }^t{\mathbb{P}}_t(s_t=s,a_t=a;\pi )$
• $V^{\pi }(s):=\mathbb{E}[{\mathrm{\Sigma }}_{t=0}^{\infty }{\gamma }^t{r}_t|s_0=s,a_t=\pi (s_t)$ for all t
  $\ge$ 0]
• $Q^{\pi }(s,a):=\mathbb{E}[{\mathrm{\Sigma }}_{t=0}^{\infty }{\gamma }^t{r}_t|s_0=s,a_0=a,a_t=\pi (s_t)$ for all t
  $\ge$ 1]
• $J(\pi ):={\mathbb{E}}_{s\sim p}[V^{\pi }(s)]$

Offline data and offline RL

• The goal of offline RL is to find a policy
  $\hat{\pi }$ —based on D— so as to minimize the expected sub-optimality with respect to the optimal policy
  ${\pi }^{\ast }$ i.e.,
  ${\mathbb{E}}_D$ [
  $J$(
  ${\pi }^{\ast }$) −
  $J$(
  $\hat{\pi }$)].

Dataset coverage assumption

• Definition 1 (Single policy concentrability) Given a policy π, define
  $C^{\pi }$to be the smallest constant that satisfies
  $d^{\pi }$(s, a)/
  $\mu$(s, a) ≤
  $C^{\pi }$ for all s ∈
  $S$ and a ∈
  $A$.

3. A warm-up: LCB in multi-armed bandits

• The multi-armed bandit (MAB) model, where S = 1 and γ = 0
• The goal of offline learning in MAB is to select an arm
  $\hat{a}$ that minimizes the expectedsub-optimality
  ${\mathbb{E}}_D$ [
  $J$(
  ${\pi }^{\ast }$) −
  $J$(
  $\hat{\pi }$)] =
  ${\mathbb{E}}_D$[r(
  $a^{\ast }$) − r(
  $\hat{a}$)]

Why does the best empirical arm fail?

• The empirical best arm is quite sensitive to the arms with a small N(a)
• Proposition 1 For any
  $ϵ$ < 0.3,
  $N$ ≥ 500, there exists a bandit problem with two arms such that for
  $\hat{a}$ =
  $argma{x}_a$
  $\hat{r}$(a), one has
  ${\mathbb{E}}_D$[r(
  $a^{\ast }$) − r(
  $\hat{a}$)] ≥
  $ϵ$.

LCB: The benefit of pessimism

• Pessimism can be deployed by first constructing a penalty function b(a).
• When b(a) captures a confidence level about the empirical reward,
  $\hat{r}$(a) − b(a) can be viewed as a lower confidence bound (LCB) on the true mean reward r(a).
• The penalty function originates from Hoeffding’s inequality
  

Is LCB optimal for solving offline multi-armed bandits?

• The following theorem shows that LCB is optimal up to a logarithmic factor when
  $C^{\ast }$ ≥ 2.
  
  
  
  
  

Imitation learning in bandit: the most played arm achieves a better rate

• Case:
  $C^{\ast }$ ∈ [1, 2).
• Assume that 1/
  $\mu$(
  $a^{\ast }$) ≤
  $C^{\ast }$.
• $\hat{a}$ =
  $argma{x}_a$
  $N(a)$.
  

Non-adaptivity of LCB

• $C^{\ast }$ = 1.5
  
  
  
• $C^{\ast }$ = 6
  
• It is impossible for LCB to achieve optimal rate in both
  $C^{\ast }$ ∈ (1, 2) and
  $C^{\ast }$ ≥ 2 regimes simultaneous.

4. LCB in contextual bandits

• The offline learning objective in CB is to find a policy
  $\hat{\pi }$ based on
  $D$.

LCB algorithm and its performance guarante

• The pessimism principle introduced for MAB can be naturally extended to CB by subtracting a penalty function b(s, a) from the empirical rewards
  $\hat{r}$(s, a) and returning
  $\hat{\pi }$(s) ∈
  $argma{x}_a$
  $\hat{r}$ (s, a) − b(s, a) for every state s.
  
  
  
• The first term has the usual statistical estimation rate of 1/
  $\sqrt{N}$.
• The second term is due to missing mass.

Optimality of LCB for solving offline contextual bandits

CB(

$C^{\ast }$) := {

$(\rho ,\mu ,R)$ |

${max}_s\rho (s)$/

$\mu (s,{\pi }^{\ast }(s)$ ≤

$C^{\ast }$ }

• On a closer inspection, in the
  $C^{\ast }$ ∈ [1, 2) regime, there is a clear separation between the informationtheoretic difficulty of offline learning in MAB, which has an exponential rate in N, and CB with at least 2 states, which has a 1/N rate.

5. LCB in Markov decision processes

Offline value iteration with LCB

Assume

$d^{\ast }(s,a)$/

$\mu (s,a)$ ≤

$C^{\ast }$

• for all
  $C^{\ast }$ ≥ 1
  
• 
  

Information-theoretic lower bound for offline RL in MDPs

• Information-theoretic limit, MDP
  
  
• The first term captures the imitation learning regime under which a fast rate 1/N is expected, while the second term deals with the large
  $C^{\ast }$ regime with a rate 1/
  $\sqrt{N}$.
• The sample complexity of VI-LCB is loose by an extra
  $1/(1-\gamma {)}^2$ factor in sample complexity.

6. Proof techniques and conjecture

• 1.When N(s,
  ${\pi }^{\ast }$(s)) = 0, this type of error, incurred by missing mass.
• 2.Standard concentration arguments tell us that
  $ϵ$ takes place with high probability, i.e., the term
  $T_2$ in the figure is no larger than
  $\delta$.
• 3.This allows us to focus on the states with large weights
• 4.Thanks to the LCB approach, the optimal action will be chosen with high probability.

Conjecture

• The LCB approach, together with value iteration is adaptively optimal for solving offline MDPs for all ranges of
  $C^{\ast }$.

7. Discussion

• We propose a new batch RL framework smoothly interpolates the two extremes of data.
• We focus on the LCB approach inspired by the principle of pessimism, we find that LCB is adaptively minimax optimal for addressing the offline learning problems in most settings.
• To provide a tighter bound for LCB in MDP.
• We expect to see our characterization of offline RL to be extended to the function approximation setting and used in the development of new offline RL algorithms that only require partial coverage.
• To analyze whether alternative conservative methods such as value regularization can achieve adaptivity and/or minimax optimality.

Reference