強化学習における多様性
恐神貴行
IBM Research – Tokyo(C) Copyright IBM Corp. 2021

1強化学習と関連技術のゲームと実社会における成功の歴史
チェッカー(1956)

バックギャモン(1992)

チェス(1997)

ビデオゲーム(2015)

囲碁(2016)

ポーカー(2017)

deepmind.com/alphago-korea

www.ibm.com/ibm/history/ibm100/us/en/icons/ibm700series/impa
cts/
en.wikipedia.org/wiki/Breakout_(video_game)researcher.watson.ibm.com/researcher/view_page.php?id=6853

カタログ送付(1960)

www.ibm.com/investor/att/pdf/BAML-AI-Conference09272018.pdf

徴税支援(2010)

www.youtube.com/watch?v=VGKp13APsBg
chicagology.com/sears/searscatalogs02/(C) Copyright IBM Corp. 2021

2

Reinforcement learning seeks to find anoptimal policy for sequential decision making
Action (𝐴𝑡 )Agent𝜋: 𝑆𝑡 → 𝐴𝑡

Observation 𝑆𝑡
Reward (𝑅𝑡 )Environment
𝑆𝑡 , 𝐴𝑡 → 𝑅𝑡 , 𝑆𝑡+1

Goal:
Maximize expected cumulative reward෍ 𝛾 𝑡 𝐄𝜋 [𝑅𝑡 ]𝑡(C) Copyright IBM Corp. 2021

3

An approach of reinforcement learning is tolearn the action-value function
Action-value function: 𝑄(𝑠, 𝑎)• Expected cumulative reward from state 𝑠 by taking action 𝑎and then following optimal policy

𝑄 𝑠, 𝑎 = 𝑅 𝑠, 𝑎+ 𝛾 ෍ 𝑝 𝑠 ′ 𝑠, 𝑎𝑠′max 𝑄 𝑠 ′ , 𝑎′𝑎′𝑠𝑎…
𝑅1

𝑅2…

𝑅3𝑄(𝑠, 𝑎)• Assume (relaxed later): Markovian 𝑠 is fully observable(C) Copyright IBM Corp. 2021

4

For most practical tasks, the action-valuefunction needs to be approximatedExponentially large state space• Combination of multiple factors• e.g. Factor: “state” of each position

Exponentially large action space• Combination of multiple “levers”• Combination of multiple agents• History of observations
Cannot deal with 𝑄(𝑠, 𝑎) in tabular form(C) Copyright IBM Corp. 2021

5

Action-value functions approximated with(deep) neural networks෠ 𝑎1 )𝑄(𝑠,෠ 𝑎2 )𝑄(𝑠,⋮Exponentially manyunits for exponentiallylarge action spacestate 𝑠Distributed representation(e.g. each unit for each pixel)(C) Copyright IBM Corp. 2021

6

Challenges in collaborative multi-agent
reinforcement learning• Exponentially many combinations of actions (team-actions)
1. How to efficiently evaluate the value of team-actions
2. How to efficiently sample good team-actions(C) Copyright IBM Corp. 2021

7Taking into account diversity inreinforcement learning(C) Copyright IBM Corp. 2021

8

Want to take relevant and diverse actions inteam sports
Zone defense

Man-to-man defense

basketballhq.com(C) Copyright IBM Corp. 2021

upload.wikimedia.org

9Consider the diversity of actions, in addition
to the value (relevance) of each action

Diversity
Value of team-action of 3 agents:
Volume2 = 𝑄(𝑠, 𝑎1 , 𝑎3 , 𝑎5 )(C) Copyright IBM Corp. 2021

10

Diversity can be represented by determinant

𝐕=Diversity
Volume2= 𝑄 𝑠, 𝑎1 , 𝑎3 , 𝑎5= det 𝐕(𝐱) 𝐕(𝐱)⊤(C) Copyright IBM Corp. 2021

𝑎1𝑎2𝑎3𝑎4𝑎5:=𝑣11 𝑣12 𝑣13𝑣21 𝑣22 𝑣23𝑣31 𝑣32 𝑣33𝑣41 𝑣42 𝑣43𝑣51 𝑣52 𝑣53:

𝐋 = 𝐕 𝐕⊤𝐱 = 1, 0, 1, 0, 1, …
𝐋 𝐱 =𝐕 𝐱 𝐕 𝐱 ⊤Indicate
selectedactions

11

Our definition of diversity (similarity) in
multi-agent reinforcement learning• The value of team-action is represented by determinant (volume)
Two actions are similar

Value is low when the two actions are taken together

Two actions are dissimilar

Value is high when the two actions are taken together

We will learn the similarity between actions accordingly(C) Copyright IBM Corp. 2021

12

We represent the action-value function withdeterminant𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡

𝑥𝑡 𝑖 = 1

𝐋𝑡

𝐋𝑡 (𝐱t )• 𝐳≤𝑡 ≡ (𝐳0 , 𝐳1 , … , 𝐳𝑡 ): Time−series of observations• 𝐳≤𝑡 = 𝑠𝑡 if Markovian state 𝑠𝑡 is observable• 𝐱𝑡 ≡ 𝜓 𝑎𝑡 ∈ 0, 1 𝑁 : Binary features of team-action 𝑎𝑡• e.g. 𝐱𝑡 indicates which actions are selected by the team
• 𝐋𝑡 : Positive semi-definite matrix (kernel) that can depend on 𝐳≤𝑡(C) Copyright IBM Corp. 2021

13

Particular structure of the kernel for effectivelearning𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡• 𝐋𝑡 ≡ 𝐕 𝐃𝑡 𝐕 ⊤• 𝐕: 𝑁 × 𝐾 matrix (𝐾 ≤ 𝑁)
• 𝐃𝑡 ≡ Diagonal exp 𝐝𝑡 𝜙
• 𝐝𝑡 𝜙 : differentiable time−series model with parameter 𝜙(e.g. RNN, LSTM, DyBM, VAR)(C) Copyright IBM Corp. 2021

14

Special case of diagonal kernel reduces to thestandard approach of ignoring diversity• 𝐋𝑡 = 𝐃𝑡 (let 𝐕 = I)
• 𝐃𝑡 ≡ Diag exp 𝐝𝑡 𝜙

• 𝐝𝑡 𝜙 : differentiable time−series model𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡= 𝛼 + 𝐝𝑡 𝜙 ⊤ 𝐱 𝑡=𝛼+෍𝑖: 𝑥𝑡 𝑖 =1

𝑑𝑡 𝜙 𝑖

𝑥𝑡 𝑖 = 1
𝐋𝑡

Sum of the values of selected actions
𝑑𝑡 𝜙 𝑖 : value of 𝑎𝑖 at time 𝑡(C) Copyright IBM Corp. 202115

Determinantal layer for diversity

state 𝑠𝑄𝜃 𝑠, 𝐱𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡
𝐋𝑡 ≡ 𝐕 Diag exp 𝐝𝑡 𝜙𝐕⊤𝐝𝑡 𝜙(C) Copyright IBM Corp. 2021

16

Prior work uses free-energy of restrictedBoltzmann machines [Sallans & Hinton 2001]
hidden unitsሚ𝐹 𝐱 = − log ෍ exp −𝐸 𝐱, 𝐡𝐛

𝐸 𝐱, 𝐡𝐖ሚ𝐡≡ −𝐛⊤ 𝐱 − 𝐜 ⊤ 𝐡 − 𝐱 ⊤ 𝐖𝐡𝐜No hidden units
𝐹 𝐱 = −𝐛⊤ 𝐱𝐡𝐱
state-action pair

Bias 𝐛 represents individual
value of each action(C) Copyright IBM Corp. 2021

17

Learning diversity via reinforcement
learning(C) Copyright IBM Corp. 2021

18

Reinforcement learning with SARSA• Tabular case𝑄 𝑠𝑡 , 𝑎𝑡 ← 𝑄 𝑠𝑡 , 𝑎𝑡 + 𝜂 TD𝑡

where TD𝑡 ≡ 𝑟𝑡+1 + 𝜌 𝑄 𝑠𝑡+1 , 𝑎𝑡+1 − 𝑄 𝑠𝑡 , 𝑎𝑡Cumulative reward
from 𝑡Cumulative reward
from 𝑡• With functional approximation: 𝑄𝜃 𝑠, 𝑎 ≈ 𝑄 𝑠, 𝑎𝜃 ← 𝜃 + 𝜂 TD𝑡 𝛻𝜃 𝑄𝜃 (𝑠𝑡 , 𝑎𝑡 )(C) Copyright IBM Corp. 2021

19

Can learn our kernel 𝐋𝑡 via SARSA in an endto-end manner• 𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡• 𝐋𝑡 ≡ 𝐕 𝐃𝑡 𝐕 ⊤• 𝐃𝑡 ≡ Diagonal exp 𝐝𝑡 𝜙

∇𝛼 𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = 1∇𝐕(ത𝐱𝑡) 𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 𝟎∇𝐕(𝐱𝑡) 𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 2 𝐕 𝐱𝑡 + ⊤∇𝜙 𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = diag 𝐕 𝐱𝑡 + 𝐕(𝐱 𝑡 ) ∇𝜙 𝐝𝑡 𝜙𝜃 ← 𝜃 + 𝜂 TD𝑡 𝛻𝜃 𝑄𝜃 (𝑠𝑡 , 𝑎𝑡 )(C) Copyright IBM Corp. 2021

20

Example: Blocker Task
• Reward• +1 when an attacker reaches the end zone
• −1 each step

• We use target positions of agents as the feature of state-action pair
• 𝐱𝑡 ≡ 𝜓 𝑎𝑡 = 𝑠𝑡+1 ∈ 0, 1 21
(C) Copyright IBM Corp. 2021

21

Determinantal SARSA finds a nearly optimal
policy 10 times faster than baseline methods
Determinantal SARSA[Heese+ 2013]
SARSA: Free-energy SARSA
NN: Neural network
EQNAC: Energy-based Q-value natural actor critic
ENATDAC: Energy-based natural TD actor critic(C) Copyright IBM Corp. 2021

22

Quality-similarity decomposition of the kernel• Value, relevance, quality
𝑞𝑖 =𝐿𝑖,𝑖• Similarity𝐪𝑆𝑖,𝑗 =𝐿𝑖,𝑗𝐋

𝐿𝑖,𝑖 𝐿𝑗,𝑗(C) Copyright IBM Corp. 2021

=𝐒𝐪

23

Value of individual actions (next positions)learned by Determinantal SARSA(C) Copyright IBM Corp. 2021

24

Similarity between actions (next positions)learned by Determinantal SARSA

Recall:Our definition of action similaritysimilar

low value whentaken together

dissimilar

high value whentaken together(C) Copyright IBM Corp. 2021

25

Stochastic Policy Task
• 2𝑁 actions• If action matches states• Get +10 reward• Hidden state transitions

01011

00101
(C) Copyright IBM Corp. 2021

26

Determinantal SARSA finds nearly optimal policies,
while baselines suffer from partial observability
Determinantal SARSA

Determinantal SARSA(𝑁 = 6)(𝑁 = 5)Determinantal SARSA(𝑁 = 8)Baselines from [Heese+ 2013]

SARSA: Free-energy SARSA
NN: Neural network
EQNAC: Energy-based Q-value natural actor critic
ENATDAC: Energy-based natural TD actor critic(C) Copyright IBM Corp. 2021

27

Choosing diverse actions(C) Copyright IBM Corp. 2021

28

Want to sample actions having high value
with high probability• 𝜀-greedy• Uniformly at random with probability 𝜀• Best action (𝑎⋆ = argmax𝑎 𝑄(𝑠, 𝑎)) with probability 1 − 𝜀Intractable for large action space• Boltzmann exploration• Take action 𝑎 with probability ∼ exp(−𝛽 𝑄(𝑠, 𝑎))• 𝛽: inverse temperature(C) Copyright IBM Corp. 202129

Choosing a diverse team-action with
Boltzmann exploration𝐱𝑡 ≡ 𝜓 𝑎𝑡 ∈ 0, 1 𝑁 :Binary features of team-action 𝑎𝑡• Our value function:𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡• Team-action selected according to Boltzmann exploration
𝜋 𝐱 𝑡 𝐳≤𝑡

exp 𝛽𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡
=σ𝐱෤ exp 𝛽𝑄𝜃 𝐳≤𝑡 , 𝐱෤det 𝐋𝑡 𝐱𝑡 𝛽
=σ𝐱෤ det 𝐋𝑡 𝐱෤ 𝛽(C) Copyright IBM Corp. 2021

30

Boltzmann exploration can be performed
efficiently when 𝛽 = 1𝜋 𝐱𝑡 𝐳≤𝑡det 𝐋𝑡 𝐱𝑡
det 𝐋𝑡 𝐱𝑡==σ𝐱෤ det 𝐋𝑡 𝐱෤
det 𝐋𝑡 + 𝐈
Determinant of 𝑁 × 𝑁 matrix

Sum over 2𝑁 terms(C) Copyright IBM Corp. 2021

31

Nearly exact Boltzmann exploration withMCMC [Kang 2013 (for 𝛽 = 1)]
1. Initialize 𝐱
2. Repeat• 𝐱 ← 𝐱′ with probability min 1,

det 𝐋𝑡𝐱′𝛽

det 𝐋𝑡 𝐱• When 𝐱’ and 𝐱 differs by one bit, det 𝐋𝑡 𝐱 ′ can be computed fromdet 𝐋𝑡 𝐱 via rank-one update techniques• Assume we can find 𝑎 ← 𝜓 −1 (𝐱)(C) Copyright IBM Corp. 2021

32

Simpler approaches:
Heuristics for more exploration and exploitation• For more exploration• Uniform with probability 𝜀• DPP with probability 1 − 𝜀• For more exploitation• Sample 𝑀 actions according to DPP• Choose the best among 𝑀• Hard-core point processes [Matérn 1986]
Any of these approaches are possible once we learn 𝐋𝑡(C) Copyright IBM Corp. 2021

33

Centralized Training and Decentralized Execution(C) Copyright IBM Corp. 2021

34

So far,

Recent trend is

Agents are trained and executedwith central control

Centralized Training andDecentralized Execution[Osogami & Raymond, AAAI-19][Yang et al., ICML 2020](C) Copyright IBM Corp. 2021

35

Centralized Training and Decentralized
Execution [Lowe+ 2017, Foerster+ 2017]
Centralized training

Decentralized execution

𝑄(𝑜 1 , 𝑜 2 , 𝑜 3 , 𝑎 1 , 𝑎 2 , 𝑎 3 )
𝜋 1 (𝑎 1 |𝑜 1 )
𝜋 3 (𝑎 3 |𝑜 3 )

𝜋 1 (𝑎 1 |𝑜 1 )

𝜋 2 (𝑎 2 |𝑜 2 )

𝜋 3 (𝑎 3 |𝑜 3 )
𝜋 2 (𝑎 2 |𝑜 2 )∇ log 𝜋 𝑖 𝑎 𝑖 𝑜 𝑖

𝑄(𝐨, 𝐚)(C) Copyright IBM Corp. 2021

36

Determinantal RL achieves state-of-the-art in
the settings of decentralized execution[Yang et al., ICML 2020](C) Copyright IBM Corp. 2021

37

Kernel studied in Yang et al., ICML 2020

Agents(2)𝑜𝑖 , 𝑎𝑗

2𝑖,𝑗𝐋𝐨𝐋(𝐨)𝑜 2 , 𝑎𝑗

2𝑗AgentsActions for all agentswith given 𝐨

Observation-action pairs
for all agents(C) Copyright IBM Corp. 2021

38

Summary(C) Copyright IBM Corp. 2021

39

Need diversity in team-actions

Our definition of action similarity
similarlow value whentaken together

dissimilar

high value whentaken together

Challenge

Our solution

Exponentially many team-actions

𝑄𝜃 𝐳≤𝑡 , 𝐱𝑡 = 𝛼 + log det 𝐋𝑡 𝐱𝑡

Efficient learning

Efficient sampling (cf. DPP)+ ⊤∇𝐕(𝐱𝑡) 𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = 2 𝐕 𝐱 𝑡∇𝜙 𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡 = diag 𝐕 𝐱𝑡 + 𝐕(𝐱𝑡 ) ∇𝜙 𝐝𝑡 𝜙𝜋 𝐱 𝑡 𝐳≤𝑡(C) Copyright IBM Corp. 2021

exp 𝛽𝑄𝜃 𝐳≤𝑡 , 𝐱 𝑡=σ𝐱෤ exp 𝛽𝑄𝜃 𝐳≤𝑡 , 𝐱෤det 𝐋𝑡 𝐱𝑡 𝛽
=σ𝐱෤ det 𝐋𝑡 𝐱෤ 𝛽40

References• T. Osogami and R. Raymond, Determinantal reinforcement learning,AAAI-19• Y. Yang et al., Multi-Agent Determinantal Q-Learning, ICML 2020

(C) Copyright IBM Corp. 2021

41