Maximum Causal Entropy Specification Inference
from Demonstrations
Marcell J. Vazquez-Chanlatte & Sanjit A. Seshia
University of California, Berkeley
Slides @ mjvc.me/CAV2020
Collaboration through Demonstrations
Demonstrations are often a natural way to relay intent.
However, it's often unclear how leverage this information.
Formal Methods
Formal Methods
Formal Methods
Formal Methods
Formal Methods
Properties of demonstrations
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Data could come from logs.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Demonstration might not be over.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Demonstration might not be over.
- Contextual : May have natual language description.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Demonstration might not be over.
- Contextual : Task specific prior.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Demonstration might not be over.
- Contextual : Task specific prior.
- Ambiguous : Not uniquely defined.
Formal Methods
Properties of demonstrations
- Noisy : Need to be robust to demonstration errors.
- Unlabeled : Demonstration might not be over.
- Contextual : Task specific prior.
- Ambiguous : Partially Ordered by Likelihood?
Formal Methods
Properties of demonstrations
- Noisy
- Unlabeled
- Contextual
- Ambiguous
Formal Methods
Goals
- Noise Resistant
- Unlabeled : Demonstration might not be over.
- Contextual : Task specific prior.
- Ambiguous : Partially Ordered by Likelihood?
Formal Methods
Goals
- Noise Resistant
- Unsupervised
- Contextual : Task specific prior.
- Ambiguous : Partially Ordered by Likelihood?
Formal Methods
Goals
- Noise Resistant
- Unsupervised
- Bayesian
Formal Methods
Goals
- Noise Resistant
- Unsupervised
- Bayesian
Contributions
- Formulate using the Principle of Maximum Causal Entropy.
- Compared to (NeurIPS 2018), explictly supports stochastic dynamics.
- Efficent implementation based on Binary Decision Diagrams.
- Experimental evaluation.
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Basic definitions
-
Assume some fixed sets of states and actions.
- A trace, $\xi$, is a sequence of states and actions.
- Assume all traces the same length, \(\tau \in \mathbb{N}\).
Basic definitions
- Assume some fixed sets of states and actions.
- A trace, $\xi$, is a sequence of states and actions.
- Assume all traces the same length, \(\tau \in \mathbb{N}\).
-
A (Boolean) specification $\varphi$, is a set of
traces.
- We say $\xi$ satisfies $\varphi$, written $\xi \models \varphi$, if $\xi \in \varphi$.
Relevant Facts about Task Specifications
-
Derived from Formal Logic, Automata, Rewards ($\epsilon$-"optimal").
Relevant Facts about Task Specifications
-
Derived from Formal Logic, Automata, Rewards ($\epsilon$-"optimal").
-
No a-priori ordering between acceptable behaviors.
Actions induce ordering
-
A demonstration of a task
$\varphi$ is an unlabeled example where
the agent tries to satisfy $\varphi$.
- Agency is key. Need a notion of action.
Actions induce ordering
-
A demonstration of a task
$\varphi$ is an unlabeled example where
the agent tries to satisfy $\varphi$. - Agency is key. Need a notion of action.
-
Success probabilities induce an ordering.
Informal Problem Statement
Informal Problem Statement
Informal Problem Statement
- Assume an agent is operating in a Markov Decision Process while trying to satisfy some unknown specification.
- Given a sequence of demonstrations, and a collection of specifications find the specification that best explains the agent's behavior.
Solution Ingredients
- Compare Likelihoods.
(This work)
-
Search for likely specifications.
(Future work)
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Inverse Reinforcement Learning
Assume agent is acting in a Markov Decision process and optimizing the sum of an unknown state reward, $r(s)$, i.e,:
Given a series of demonstrations, what reward, $r(s)$, best explains the behavior? (Abbeel and Ng 2004)
Inverse Reinforcement Learning
Given a series of demonstrations, what reward, $r(s)$, best explains the behavior? (Abbeel and Ng 2004)
- Problem: There is no unique solution as posed! \[ \Pr(r~|~\xi) = ? \]
- Idea: Disambiguate via the Principle of Maximum Causal Entropy. (Ziebart, et al. 2010)
Principle Maximum Causal Entropy Intuition
Causally Conditioning
Current actions shouldn't depend on
information from the future.
Principle Maximum Causal Entropy Intuition
Causally Conditioning
Current actions shouldn't depend on
information from the future.
Principle Maximum Causal Entropy Intuition
Key Idea: Don't commit to any particular prediction more than the data forces you too.
Informally: Minimize surprise of actions.
subject to feature matching.
Principle Maximum Causal Entropy Intuition
Key Idea: Don't commit to any particular prediction more than the data forces you too.
Formally: Maximize expected causal entropy.
Principle Maximum Causal Entropy Intuition
Key Idea: Don't commit to any particular prediction more than the data forces you too.
Formally: Maximize expected causal entropy.
Principle Maximum Causal Entropy Intuition
Maximize
Principle Maximum Causal Entropy Intuition
Maximize
Minimum Entropy Forcaster
Principle Maximum Causal Entropy Intuition
Maximize
Maximum Entropy Forcaster
Principle Maximum Causal Entropy Intuition
Key Take Away
Maximum Causal Entropy → Robust Forecaster
Linear Rewards
Consider case where reward is linear combination of state features.
Linear Rewards
Consider case where reward is linear combination of state features.
Linear Rewards
Suppose we observe: \(\mathbb{E}[\vec{f}]\)
Maximum Causal Entropy Policy
Linear Rewards
Suppose we observe: \(\mathbb{E}[\vec{f}]\)
Maximum Causal Entropy Policy
Fit \(\theta\) to match \(\mathbb{E}[\vec{f}]\)
Resulting policy is the one with maximum causal entropy.
(Ziebart, et al. 2010)
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Q: What should the reward be?
Proposal: Use indicator.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Note: States are now traces.
Let's exactly define the transition dynamics.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Note: States are now traces.
Suppose \(\varphi\) is over traces of length 2.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Note: States are now traces.
Suppose \(\varphi\) is over traces of length 2.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
States now correspond to paths in unrolled tree.
Suppose \(\varphi\) is over traces of length 2.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Maximum Causal Entropy Policy
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Maximum Causal Entropy Policy
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Maximum Causal Entropy Policy
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Maximum Causal Entropy Policy
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Maximum Causal Entropy Policy
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Note: Satisfaction probability grow monotonically in \(\theta\).
Can binary search for \(\theta\) such that satisfaction probability matches data.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Problem: Unrolled tree grows exponentially in horizon!
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Observation 1: A lot of shared structure in computation graph.
Observation 2: System and environment actions are ordered.
Idea: Reduce Specification Inference to Maximum Entropy IRL.
Idea: Encode to binary predicate
\[
\psi: \{0, 1\}^n \to \{0,1\}
\]
and represent as Reduced Ordered Binary Decision Diagram
(Bryant 1986).
Structure of the talk
Prelude - Problem Setup
Act 1 - Naïve Problem Formulation
Act 2 - Efficent Encoding using Binary Decision Diagrams
Finale - Experiment
Summary
For time, focus on describing BDD encoding.
Random Bit Model
Idea: Model Markov Decision Process as deterministic transition system with access to $n_c$ coin flips.
Note: Principle of maximum causal entropy + finite horizon together are robust to small dynamics mismatches.
Random Bit Model
Next: Assume \(\#(\text{Actions}) = 2^{n_a} \)
Random Bit Model
Next: Assume \(\#(\text{Actions}) = 2^{n_a} \)
Random Bit Model
Unrolling \(\tau\) steps and composing with specification results in a predicate.
Random Bit Model
Proposal: Represent \(\psi\) as Binary Decision Diagram with bits in causal order.
Random Bit Model
Proposal: Represent \(\psi\) as Binary Decision Diagram with bits in causal order.
Maximum Causal Entropy and BDDs
Q: Can Maximum Entropy Causal Policy be computed on causally ordered BDDs?
Maximum Causal Entropy and BDDs
Q: Can Maximum Entropy Causal Policy be computed on causally ordered BDDs?
A: Yes! Due to:
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
\[ \text{smax}(\alpha_1, \ldots, \alpha_4) = \ln(\sum_{i=1}^4 e^{\alpha_i}) \]
Maximum Causal Entropy and BDDs
Q: Can Maximum Entropy Causal Policy be computed on causally ordered BDDs?
A: Yes! Due to:
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
\[ \text{smax}(\alpha_1, \ldots, \alpha_4) = \ln(e^{\ln(e^{\alpha_1}+ e^{\alpha_2})} + e^{\ln(e^{\alpha_3}+ e^{\alpha_4})}) \]
Maximum Causal Entropy and BDDs
Q: Can Maximum Entropy Causal Policy be computed on causally ordered BDDs?
A: Yes! Due to:
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
\[ \text{smax}(\alpha_1, \ldots, \alpha_4) = \text{smax}(\text{smax}(\alpha_1, \alpha_2), \text{smax}(\alpha_3, \alpha_4)) \]
Maximum Causal Entropy and BDDs
Q: Can Maximum Entropy Causal Policy be computed on causally ordered BDDs?
A: Yes! Due to:
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
- \(\text{smax}(\alpha, \alpha) = \alpha + \ln(2)\)
- \(\text{E}(\alpha, \alpha) = \alpha\)
Maximum Causal Entropy and BDDs
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
- \(\text{smax}(\alpha, \alpha) = \alpha + \ln(2)\)
- \(\text{E}(\alpha, \alpha) = \alpha\)
Maximum Causal Entropy and BDDs
- Associativity of \(\text{smax}\) and \(\mathbb{E}\).
- \(\text{smax}(\alpha, \alpha) = \alpha + \ln(2)\)
- \(\text{E}(\alpha, \alpha) = \alpha\)
Size Bounds
Q: How big can these Causal BDDs be?
Size Bounds
Linear in horizon!
Note: Using function composition, can build BDD in polynomial time.
Summary
Summary
Structure of the talk
Prelude - Problem Setup
Act 1 - Naive Reduction to Maximum Causal Entropy IRL
Act 2 - The Random Bit Model and BDD Based Encoding
Finale - Experiment
Toy Experiment
Toy Experiment
Dynamics
- Agent can attempt to move {↑, ↓, ←, →}.
- With probability \(\frac{1}{32}\), agent will slip and move ←.
Toy Experiment
Dynamics
- A = {↑, ↓, ←, →}.
- \(p = \frac{1}{32}\), slip and move ←.
Toy Experiment
Dynamics
- A = {↑, ↓, ←, →}.
- \(p = \frac{1}{32}\), slip and move ←.
Provided 6 unlabeled demonstrations for the task:
- Go to and stay at the yellow tile (recharge).
- Avoid red tiles (lava).
- If you enter a blue, touch a brown tile before recharging.
- Within 10 time steps.
Note: Dashed demonstration fails to dry off due to slipping.
Toy Experiments
Dynamics
- A = {↑, ↓, ←, →}.
- \(p = \frac{1}{32}\), slip and move ←.
| Spec | Policy Size | ROBDD | Relative Log Likelihood |
| (#nodes) | build time | (Compared to True) | |
| true | 1 | 0.48s | 0 |
| φ1 = Avoid Lava | 1797 | 1.5s | -22 |
| φ2= Recharge | 1628 | 1.2s | 5 |
| φ3= Don't recharge while wet | 750 | 1.6s | -10 |
| φ4 = φ1 ∧ φ2 | 523 | 1.9s | 4 |
| φ5 = φ1 ∧ φ3 | 1913 | 1.5s | -2 |
| φ6 = φ2 ∧ φ3 | 1842 | 2s | 15 |
| φ⋆ = φ1 ∧ φ2 ∧ φ3 | 577 | 1.6 | 27 |
| (smaller better) | (smaller better) | (bigger better) |
Toy Experiments
Dynamics
- A = {↑, ↓, ←, →}.
- \(p = \frac{1}{32}\), slip and move ←.
Find ipython binder for experiment at:
bit.ly/2WgzDcW
Code for this paper:
github.com/mvcisback/mce-spec-inference
Informal Problem Statement
Formal Methods
Goals
- Noise Resistant
- Unsupervised
- Bayesian
Contributions
- Formulate using the Principle of Maximum Causal Entropy.
- Compared to (NeurIPS 2018), explictly supports stochastic dynamics.
- Efficent implementation based on Binary Decision Diagrams.
- Experimental evaluation.
Solution Ingredients
-
Compare Likelihoods.
(This work)
-
Search for likely specifications.
(Future work)
Communicating via Demonstrations
(Future Work)
Maximum Causal Entropy Specification Inference
from Demonstrations
Marcell J. Vazquez-Chanlatte & Sanjit A. Seshia
University of California, Berkeley
Slides @ mjvc.me/CAV2020
Motivating Questions
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Did the agent intend to touch the red tile?
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Did the agent intend to touch the red tile? A: Probably Not.
p
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Can we automatically infer agent intent?
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Can we automatically infer agent intent? A: Stay tuned!
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Can we automatically infer agent intent? A: Stay tuned!
Q: How should we represent intent?
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Can we automatically infer agent intent? A: Stay tuned!
Q: How should we represent intent? A: Formal Specifications?
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: What is the agent likely to do in the future?
Consider an agent acting in the following stochastic grid world.
Motivating Questions
Q: Can we algorithmically forecast the agent's behavior?