[reading] Reinforcement and Imitation Learning via Interactive No-Regret Learning

The paper presents new methods for imitation and reinforcement learning that leverage cost-to-go information within an interactive no-regret learning framework. Key contributions include the AGGREVATE algorithm for imitation learning and a related algorithm for reinforcement learning, both offering strong theoretical guarantees.

Meta

• Authors: Stéphane Ross, J. Andrew Bagnell
• Institution: The Robotics Institute, Carnegie Mellon University
• Date: June 23, 2014
• Link: https://arxiv.org/pdf/1406.5979

Key Contributions

1. AGGREVATE Algorithm:
   • Purpose: Extends DAGGER by minimizing long-term cost-to-go instead of just immediate classification loss.
   • Method:
     1. Collect data by observing the expert and performing random explorations.
     2. Observe the resulting cost-to-go \(Q\).
     3. Train policies \(\hat{\pi}_n\) to minimize these costs.
   • Algorithm Steps:

     Initialize $$D \leftarrow \emptyset$$, $$\hat{\pi}_1 \leftarrow any policy in \Pi$$
     for $$i = 1$$ to $$N$$ do
         Collect $$m$$ data points as follows:
             for $$j = 1$$ to $$m$$ do
                 Sample uniformly $$t \in \{1, 2, \ldots, T\}$$
                 Start new trajectory in initial state $$s_1$$
                 Execute current policy $$\hat{\pi}_i$$ up to time $$t-1$$
                 Explore action $$a_t$$ in state $$s_t$$
                 Execute expert from time $$t+1$$ to $$T$$, observe cost-to-go $$Q$$
                 Add $$(s, t, a, Q)$$ to dataset $$D$$
         Train cost-sensitive classifier $$\hat{\pi}_{i+1}$$ on $$D$$
     Return best $$\hat{\pi}_i$$ on validation
     

2. No-Regret Policy Iteration (NRPI):
   • Purpose: Adapts AGGREVATE for reinforcement learning using cost-to-go estimates.
   • Method:
     1. Collect cost-to-go examples by sampling from state distributions \(u_t\).
     2. Explore actions and apply the current policy to estimate future costs.
     3. Train policies using a no-regret online learning algorithm.
   • Algorithm Steps:

     Initialize $$D \leftarrow \emptyset$$, $$\hat{\pi}_1 \leftarrow any policy in \Pi$$
     for $$i = 1$$ to $$N$$ do
         Collect $$m$$ data points as follows:
             for $$j = 1$$ to $$m$$ do
                 Sample uniformly $$t \in \{1, 2, \ldots, T\}$$
                 Sample state $$s_t$$ from exploration distribution $$
     u_t$$
                 Execute exploration action $$a_t$$ in state $$s_t$$
                 Execute current policy $$\hat{\pi}_i$$ from time $$t+1$$ to $$T$$, observe cost-to-go $$Q$$
                 Add $$(s, a, t, Q)$$ to dataset $$D$$
         Train cost-sensitive classifier $$\hat{\pi}_{i+1}$$ on $$D$$
     Return best $$\hat{\pi}_i$$ on validation
     

Key Equations and Theoretical Guarantees

1. Performance Metric:
   • Total cost of executing policy \(\pi\) over \(T\) steps: \(J(\pi) = \sum_{t=1}^{T} \mathbb{E}_{s \sim d_t^\pi} [C(s, \pi(s))]\)
2. Cost-to-Go Function:
   • Expected future cost-to-go of executing action \(a\) in state \(s\) followed by policy \(\pi\) for \(t-1\) steps: \(Q^\pi_t(s, a)\)
3. AGGREVATE Theoretical Guarantee:
   • If a no-regret algorithm is used, as \(N \to \infty\): \(\lim_{N o \infty} J(\pi) \leq J(\pi^*) + T \epsilon_{ ext{class}}\)
4. NRPI Theoretical Guarantee:
   • For any policy \(\pi'\): \(J(\hat{\pi}) \leq J(\pi) \leq J(\pi') + T \epsilon_{ ext{regret}} + T Q_{\max} D( u, \pi')\)
   • If a no-regret algorithm is used, as \(N \to \infty\): \(\lim_{N o \infty} J(\pi) \leq J(\pi') + T Q_{\max} D( u, \pi')\)

Conclusion

By integrating cost-to-go information into no-regret learning frameworks, the paper presents significant advancements in both imitation learning and reinforcement learning. The proposed algorithms, AGGREVATE and NRPI, offer a unified approach with strong theoretical guarantees, enhancing the stability and effectiveness of learned policies in practical applications.