1

Federated Methods to speed up Reinforcement Learning

Sajad Khodadadian

Georgia Institute of Technology

2

Reinforcement Learning

3

Reinforcement Learning

My research: Theoretical Foundations of Reinforcement Learning

This talk: Federated Reinforcement Learning

4

Kendall et. al.: “Learning to Drive in a Day”, 2018

Reinforcement Learning

RL is data intensive!

factordaily.com

Multiple data collecting agents

5

Reinforcement Learning

shengpu-tang.me

Privacy matters!

6

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

7

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

8

​

​

​

​

Background on MDP Theory

Agent

Environment

9

Background on MDP Theory

Discount factor

Reward function

Initial state and action

policy

10

​

​

​

​

Background on MDP Theory

…

• TD-learning

Markovian noise

11

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

12

Vanilla Distributed Reinforcement Learning

12

Agent 1

Central Agent

Agent j

Local Agents

• Do not want to send data
• Privacy concerns

13

• Do not want to send data
• Privacy concerns

Federated Reinforcement Learning

Agent 1

Local observations & policy

not shared with central agent

Agent j

14

Federated Reinforcement Learning

¹Shen, et al. "Asynchronous advantage actor critic: Non-asymptotic analysis and linear speedup." arXiv preprint arXiv:2012.15511 (2020).

Conjecture

Yes! We are the first to show this.

Open problem: is there linear speedup in federated RL?

15

16

​

​

​

​

Convergence

Bias

Convergence Variance

17

​

​

​

​

Convergence

Bias

Convergence Variance

Higher order

18

Federated TD-learning

Agent 1

Agent j

19

Linear Speedup in Federated TD-Learning

20

• Federated Supervised Learning:

​

​

​

• Federated Reinforcement Learning:

​

​

​

​

Linear Speedup in Federated Learning

• Linear speedup is possible [Khaled, et. al. ‘20], [Spiridonoff, et. al. ‘21], [….]
• Key ingredient in these results: The noise is i.i.d.

​

​

• [Wai ’20] [Zeng, et. al., ‘20]
• They have linear penalty
• Key challenge: Markov noise.
• Linear speedup in federated TD-learning under i.i.d. noise assumption [Shen, et. al., ‘20]

​

​

21

​

​

Stochastic Approximation

TD-learning, off-policy

TD-learning, on-policy:

Contraction

22

​

​

Stochastic Approximation

Extend to Federated!

23

​

​

Federated Stochastic Approximation (FedSAM)

Agent 1

Agent j

…

24

​

​

Federated Stochastic Approximation (FedSAM)

25

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

26

​

​

​

​

Proof Outline

• i.i.d. noise
• Markovian noise

• Markovian noise

27

​

​

​

​

Proof Outline

variance

28

​

​

​

​

Proof Outline

variance

Moreau envelop

Refined analysis

29

​

​

​

​

Multiple Agents, Synchronous, i.i.d. Noise

30

​

​

​

​

Multiple Agents, Synchronous, Markovian Noise

?

?

?

?

Our refined analysis:

Simple bound

31

​

​

​

​

Multiple Agents, Synchronous, Markovian Noise

Mixing time

32

​

​

​

​

Multiple Agents, Asynchronous, Markovian Noise

Consensus error due to local updates

33

​

​

Key Takeaways

1. Federated Reinforcement Learning

​

​

• Key ideas in the proof

​

• Lyapunov argument
• Refined analysis based on Markov chain mixing
• Analysis of synchronization error separately

34

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

35

​

​

​

​

My other works

Focus of this talk

Focus of my other work

36

​

​

​

My other works

Actor-Critic

Critic

Actor

​

• Finite Sample Analysis of Off-policy Natural Actor-Critic Algorithm[KCM, International Conference on Machine Learning ‘20]

​

• Finite Sample Analysis of Off-policy Natural Actor-Critic Algorithm With Linear Function Approximation [CKM, IEEE Control Syst. Lett. ‘22] [CKM , CDC ‘22]

​

​

​

suboptimal

37

​

​

​

My other works

Actor-Critic

Critic

Actor

• On the Linear (and Super-Linear) Convergence of Natural Policy Gradient Algorithm [KJVM, Syst. Control. Lett. ‘22], [KJVM, CDC ‘21]

38

​

​

​

My other works

Actor-Critic

Critic

Actor

• Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm [KDMJ, IEEE Trans. Automat. Contr. ‘22]

Two-Time-Scale Actor-Critic

39

​

​

​

​

My other works

• I also have two pieces of work on Information Theoretic Fairness in Machine Learning

40

Outline

• Background on Reinforcement Learning
• Federated Reinforcement Learning

​

• My other works
• Future research directions

• Proof sketch

41

​

​

​

​

Multi Time-Scale Stochastic Approximation

Safe Reinforcement Learning

Markov games

Multi-agent Reinforcement Learning

42

​

​

​

​

Reinforcement Learning for Operations Research

43

​

​

​

​

Fairness in Reinforcement Learning

Fairness

​

44

Multi-Agent Systems

Reinforcement Learning

Fairness

Stochastic Processes

Control Theory

Information Theory

Optimization

Dynamic Programming