#  _Retrospective:_ Flipping Bits in Memory Without Accessing Them:
An Experimental Study of DRAM Disturbance Errors

Onur Mutlu
_ETH Zürich_

###### Abstract

Our ISCA 2014 paper [1] provided the first scientific and detailed
characterization, analysis, and real-system demonstration of what is now
popularly known as the RowHammer phenomenon (or vulnerability) in modern
commodity DRAM chips, which are used as main memory in almost all modern
computing systems. It experimentally demonstrated that more than 80% of all
DRAM modules we tested from the three major DRAM vendors were vulnerable to
the RowHammer read disturbance phenomenon: one can predictably induce bitflips
(i.e., data corruption) in real DRAM modules by repeatedly accessing a DRAM
row and thus causing electrical disturbance to physically nearby rows. We
showed that a simple unprivileged user-level program induced RowHammer
bitflips in multiple real systems and suggested that a security attack can be
built using this proof-of-concept to hijack control of the system or cause
other harm. To solve the RowHammer problem, our paper examined seven different
approaches (including a novel probabilistic approach that has very low cost),
some of which influenced or were adopted in different industrial products.

Many later works from various research communities examined RowHammer,
building real security attacks, proposing new defenses, further analyzing the
problem at various (e.g., device/circuit, architecture, and system) levels,
and exploiting RowHammer for various purposes (e.g., to reverse-engineer DRAM
chips). Industry has worked to mitigate the problem, changing both memory
controllers and DRAM standards/chips. Two major DRAM vendors finally wrote
papers on the topic in 2023, describing their current approaches to mitigate
RowHammer. Research & development on RowHammer in both academia & industry
continues to be very active and fascinating.

This short retrospective provides a brief analysis of our ISCA 2014 paper and
its impact. We describe the circumstances that led to our paper, mention its
influence on later works and products, describe the mindset change we believe
it has helped enable in hardware security, and discuss our predictions for
future.

##  I Background and Circumstances

Our stumbling on the RowHammer problem and creation of its first scientific
analysis happened as a result of a confluence of multiple factors. First, my
group was working on DRAM technology scaling issues since late 2010. We were
very interested in failure mechanisms that appear or worsen due to aggressive
technology scaling. To study such issues (e.g., data retention errors [2]), we
built an FPGA-based DRAM testing infrastructure [2] between 2011-2012, which
we later open sourced as SoftMC [3, 4] and DRAM Bender [5, 6]. Second, around
the same timeframe, we were investigating similar technology scaling issues in
flash memory using real NAND flash chips [7, 8]. We knew read disturbance
errors were significant in NAND flash memory [7, 9, 8, 10, 11] and were very
interested in how prevalent they were in DRAM. Third, we were collaborating
with Intel (e.g., [2]) to understand and solve DRAM technology scaling
problems and build our DRAM infrastructure. Three of my students and I spent
the summer of 2012 at Intel to work closely with our collaborators (two are
co-authors): during this time, we finalized the calibration and stabilization
of our infrastructure and had significant technical discussions and
experimentation on DRAM scaling problems.

Although there was awareness of the RowHammer problem in industry in 2012 (see
Footnote 1 in [1]), there was no comprehensive experimental analysis and
detailed real-system demonstration of it. We believed it was critical to
provide a rigorous scientific analysis using a wide variety of DRAM chips and
scientifically establish major characteristics and prevalence of RowHammer.
Hence, in the summer of 2012, we set out to use our DRAM testing
infrastructure to analyze RowHammer. Our initial results showed how widespread
the read disturbance problem was across the (at the time) recent DRAM chips we
tested, so we studied the problem comprehensively and developed many solutions
to it. The resulting paper was submitted to MICRO in May 2013 but was
rejected. We strengthened the results, especially of the mitigation mechanisms
and the number of tested chips, and made the analysis more comprehensive
before it was accepted to ISCA 2014 (2 of the 6 reviewers still rejected it
for interesting reasons).

##  II Major Contribution and Influence

The major contribution of our paper is the exposure and detailed analysis of a
fundamental hardware failure mechanism that breaks memory isolation in real
systems and thus has huge implications on system reliability, security, and
safety. Our paper is a comprehensive study of a major DRAM technology scaling
problem, RowHammer, including its first scientific analysis, experimental
characterization, real system demonstration, and solutions with their
evaluation. To our knowledge, RowHammer is the first example of a hardware
failure mechanism that creates a significant and widespread system security
vulnerability [12, 13, 14, 15], as our ISCA 2014 paper suggested.

Our work has had large influence on both industry & academia. Individual
follow-on works are many to list here; we refer the reader to longer invited
retrospectives we wrote [12, 13, 14]. We give major examples of influence,
focusing on RowHammer’s effect on the collective mindset of security research
and major industry milestones related to RowHammer.

RowHammer Attacks & Mindset Shift in Hardware Security. Our demonstration that
one can easily and predictably induce bitflips in commodity DRAM chips using a
real user-level program enabled a major mindset shift in hardware security. It
showed that general-purpose hardware is fallible in a very widespread manner
and its problems are exploitable. Tens of works (see [14, 13]) built directly
on our work to exploit RowHammer bitflips to develop many attacks that
compromise system integrity and confidentiality, starting from the first
RowHammer exploit by Google Project Zero in 2015 [16, 17] to recent works in
2022-2023 (e.g., [18, 19]). These attacks showed increasingly sophisticated
ways by which an unprivileged attacker can exploit RowHammer bitflips to
circumvent memory protection and gain complete control of a system (e.g., [16,
20, 21, 22, 23, 24, 25, 26, 27, 28]), gain access to confidential data (e.g.,
[29, 18, 19]), or maliciously destroy the safety and accuracy of a system,
e.g., an otherwise accurate machine learning inference engine (e.g., [30,
31]). The mindset enabled by RowHammer bitflips caused a renewed interest in
hardware security research, enticing many researchers to deeply understand
hardware’s inner workings and find new vulnerabilities. Thus, hardware
security issues have become mainstream discussion in top security &
architecture venues, some having sessions entitled RowHammer.

RowHammer Defenses. Tens of works proposed mitigations against RowHammer, some
of which were inspired by the solutions we discussed in our ISCA 2014 paper.
To date, the search for more efficient and low-cost RowHammer solutions
continues. We refer the reader to our prior overview papers [14, 13, 32] and
more recent works in 2023 (e.g., [33, 34, 35]).

RowHammer Analyses. Our paper initiated works at both architectural &
circuit/device-levels to better understand RowHammer and reverse-engineer DRAM
chips, to develop better models, defenses, and attacks (see [14, 13]). Our
ISCA’20 work [36] revisited RowHammer, comprehensively analyzed of 1580 DRAM
chips of three different types from at least two generations, showing that
RowHammer has gotten much worse with technology scaling & existing solutions
are not effective at future vulnerability levels.

Industry Reaction: Attacks, Analyses, and Mitigations. Folks developing
industrial memory testing programs immediately included RowHammer tests, e.g.,
in memtest86 [37], citing our work. Industry needed to immediately protect
RowHammer-vulnerable chips already in the field, so almost all system vendors
increased refresh rates; a solution we examined in our paper and deemed costly
for performance and energy, yet it was the only practical lever that could be
used in the field. Apple publicly acknowledged our work in their security
release [38] that announced higher refresh rates to mitigate RowHammer. Intel
designed memory controllers that performed probabilistic activations (i.e.,
pTRR [39, 40]), similar to our PARA solution [1]. DRAM vendors modified the
DRAM standard to introduce TRR (target row refresh) mechanisms [39] and
claimed their new DDR4 chips to be RowHammer-free [39, 41]. This bold claim
was later refuted by our TRRespass work [39] in 2020, which introduced the
many-sided RowHammer attack to circumvent internal protection mechanisms added
to the DRAM chips. Our later work, Uncovering TRR [41] showed that one can
almost completely reverse-engineer and thus easily bypass RowHammer
mitigations employed in all tested DRAM chips, i.e., RowHammer solutions in
DRAM chips are broken. The analysis done by our two major works in 2020 [39,
36] caused the industry to reorganize the RowHammer task group at JEDEC, which
produced two white papers on mitigating RowHammer [42, 43]. Nine years after
our paper, in 2023, two major DRAM vendors, SK Hynix and Samsung, finally
wrote papers [44, 45] on the RowHammer problem, describing their solutions.
Several of these industry solutions build on the probabilistic & access-
counter-based solution approaches our ISCA 2014 paper introduced.

Major Internet and cloud systems companies also took a deep interest in
RowHammer as it can greatly impact their system security, dependability, and
availability. Multiple works from Google, e.g., by Google Project Zero in 2015
[16, 17] and Half Double in 2021-2022 [46] directly built on our paper to
demonstrate attacks in real systems. Researchers from Microsoft have developed
deeper analyses of RowHammer [47], along with new RowHammer attacks [48] and
defenses (e.g., [49, 50, 51, 48]).

##  III Summary and Future Outlook

Since 2012-2014, RowHammer vulnerability has become much worse due to
technology scaling: without mitigation, one can now induce RowHammer bitflips
with orders of magnitude smaller number of activations (e.g., $\sim$10K) and
cause much higher rates of errors in cutting-edge DRAM chips [36, 41].
Sophisticated attacks are continuously developed to circumvent the mitigations
employed in real DRAM chips. Fortunately, we have also come a long way in
further understanding and better mitigating the RowHammer vulnerability. The
industry is now (hopefully) fully aware of the importance of the problem and
of avoiding bitlips. Unfortunately, an efficient and completely-secure
solution is not found yet. The solution space poses a rich area of tradeoffs
in terms of security, performance, power/energy, cost/complexity. All
solutions forego some desirable properties in favor of others. As such, a
critical direction for the future is to find solutions superior to what we
have today. We believe system-DRAM cooperation [52, 14] will be important to
enabling complete solutions. We also believe it is critical to deeply
understand the properties of RowHammer under many different conditions so that
we can develop effective solutions that work under all circumstances.
Unfortunately, we do not yet fully understand many facets of RowHammer (see
[14, 53, 54, 55]).

DRAM technology scaling will continue to create problems that will exacerbate
the bitflips and the resulting robustness (i.e., safety/security/reliability)
problems. Our ISCA 2023 paper on RowPress [55] provides the first scientific
and detailed characterization, analysis, and real-system demonstration of yet
another read disturbance mechanism in DRAM. What other fascinating problems
will we see and can we completely solve them efficiently? Will we ever be free
of bitflips at the system and application levels?

## References

  * [1] Y. Kim _et al._ , “Flipping Bits in Memory Without Accessing Them: An Experimental Study of DRAM Disturbance Errors,” in _ISCA_ , 2014.
  * [2] J. Liu _et al._ , “An Experimental Study of Data Retention Behavior in Modern DRAM Devices: Implications for Retention Time Profiling Mechanisms,” _ISCA_ , 2013.
  * [3] H. Hassan _et al._ , “SoftMC: A Flexible and Practical Open-Source Infrastructure for Enabling Experimental DRAM Studies,” in _HPCA_ , 2017\.
  * [4] SoftMC Source Code, https://github.com/CMU-SAFARI/SoftMC.
  * [5] A. Olgun _et al._ , “DRAM Bender: An Extensible and Versatile FPGA-based Infrastructure to Easily Test State-of-the-art DRAM Chips,” _TCAD_ , 2023\.
  * [6] “DRAM Bender,” https://github.com/CMU-SAFARI/DRAM-Bender.
  * [7] Y. Cai _et al._ , “Error Patterns in MLC NAND Flash Memory: Measurement, Characterization, and Analysis,” in _DATE_ , 2012.
  * [8] Y. Cai _et al._ , “Error Analysis and Retention-Aware Error Management for NAND Flash Memory,” _ITJ_ , 2013.
  * [9] Y. Cai _et al._ , “Program Interference in MLC NAND Flash Memory: Characterization, Modeling, and Mitigation,” in _ICCD_ , 2013.
  * [10] Y. Cai _et al._ , “Read Disturb Errors in MLC NAND Flash Memory: Characterization, Mitigation, and Recovery,” in _DSN_ , 2015.
  * [11] Y. Cai _et al._ , “Error Characterization, Mitigation, and Recovery in Flash Memory Based Solid-State Drives,” _Proc. IEEE_ , 2017.
  * [12] O. Mutlu, “The RowHammer Problem and Other Issues we may Face as Memory Becomes Denser,” _DATE_ , 2017.
  * [13] O. Mutlu and J. Kim, “RowHammer: A Retrospective,” _IEEE TCAD Special Issue on Top Picks in Hardware and Embedded Security_ , 2019.
  * [14] O. Mutlu _et al._ , “Fundamentally Understanding and Solving RowHammer,” in _ASP-DAC_ , 2023.
  * [15] T. Dullien, “Security, Moore’s Law, and the Anomaly of Cheap Complexity,” in _CCDCOE_ , 2018, https://www.youtube.com/watch?v=q98foLaAfX8.
  * [16] M. Seaborn and T. Dullien, “Exploiting the DRAM Rowhammer Bug to Gain Kernel Privileges,” http://googleprojectzero.blogspot.com.tr/2015/03/exploiting-dram-rowhammer-bug-to-gain.html, 2015\.
  * [17] M. Seaborn and T. Dullien, “Exploiting the DRAM Rowhammer Bug to Gain Kernel Privileges,” _Black Hat_ , 2015.
  * [18] A. S. Rakin _et al._ , “DeepSteal: Advanced Model Extractions Leveraging Efficient Weight Stealing in Memories,” in _S &P_, 2022.
  * [19] K. Mus _et al._ , “Jolt: Recovering TLS Signing Keys via Rowhammer Faults,” in _S &P_, 2023.
  * [20] D. Gruss _et al._ , “Rowhammer.js: A Remote Software-Induced Fault Attack in Javascript,” in _DIMVA_ , 2016.
  * [21] V. van der Veen _et al._ , “Drammer: Deterministic Rowhammer Attacks on Mobile Platforms,” in _CCS_ , 2016.
  * [22] Y. Xiao _et al._ , “One Bit Flips, One Cloud Flops: Cross-VM Row Hammer Attacks and Privilege Escalation,” in _USENIX Security_ , 2016.
  * [23] K. Razavi _et al._ , “Flip Feng Shui: Hammering a Needle in the Software Stack,” _USENIX Security_ , 2016.
  * [24] A. Tatar _et al._ , “Throwhammer: Rowhammer Attacks Over the Network and Defenses,” in _USENIX ATC_ , 2018.
  * [25] M. Lipp _et al._ , “Nethammer: Inducing Rowhammer Faults Through Network Requests,” arXiv:1805.04956, 2018.
  * [26] L. Cojocar _et al._ , “Exploiting Correcting Codes: On the Effectiveness of ECC Memory Against Rowhammer Attacks,” in _S &P_, 2019.
  * [27] F. de Ridder _et al._ , “SMASH: Synchronized Many-Sided Rowhammer Attacks from JavaScript,” in _USENIX Security_ , 2021.
  * [28] P. Jattke _et al._ , “Blacksmith: Scalable Rowhammering in the Frequency Domain,” in _S &P_, 2022.
  * [29] A. Kwong _et al._ , “RAMBleed: Reading Bits in Memory Without Accessing Them,” in _S &P_, 2020.
  * [30] S. Hong _et al._ , “Terminal Brain Damage: Exposing the Graceless Degradation in Deep Neural Networks Under Hardware Fault Attacks,” in _SS_ , 2019.
  * [31] F. Yao _et al._ , “Deephammer: Depleting the Intelligence of Deep Neural Networks Through Targeted Chain of Bit Flips,” in _USENIX Security_ , 2020\.
  * [32] A. G. Yağlıkcı _et al._ , “BlockHammer: Preventing RowHammer at Low Cost by Blacklisting Rapidly-Accessed DRAM Rows,” in _HPCA_ , 2021.
  * [33] M. Marazzi _et al._ , “ProTRR: Principled yet Optimal In-DRAM Target Row Refresh,” in _S &P_, 2023.
  * [34] M. Wi _et al._ , “SHADOW: Preventing Row Hammer in DRAM with Intra-Subarray Row Shuffling,” in _HPCA_. IEEE, 2023.
  * [35] J. Juffinger _et al._ , “CSI: Rowhammer–Cryptographic Security and Integrity against Rowhammer (to appear),” in _S &P_, 2023.
  * [36] J. S. Kim _et al._ , “Revisiting RowHammer: An Experimental Analysis of Modern DRAM Devices and Mitigation Techniques,” in _ISCA_ , 2020.
  * [37] PassMark Software, “MemTest86: The Original Industry Standard Memory Diagnostic Utility,” http://www.memtest86.com/troubleshooting.htm, 2015\.
  * [38] Apple Inc., “About the Security Content of Mac EFI Security Update 2015-001,” https://support.apple.com/en-us/HT204934, 2015.
  * [39] P. Frigo _et al._ , “TRRespass: Exploiting the Many Sides of Target Row Refresh,” in _S &P_, 2020.
  * [40] M. Kaczmarski, “Thoughts on Intel Xeon E5-2600 v2 Product Family Performance Optimisation – Component Selection Guidelines,” http://infobazy.gda.pl/2014/pliki/prezentacje/d2s2e4-Kaczmarski-Optymalna.pdf, page 13, 2014.
  * [41] H. Hassan _et al._ , “Uncovering In-DRAM RowHammer Protection Mechanisms: A New Methodology, Custom RowHammer Patterns, and Implications,” in _MICRO_ , 2021.
  * [42] JEDEC, _JEP300-1: Near-Term DRAM Level RowHammer Mitigation_ , 2021.
  * [43] JEDEC, _JEP301-1: System Level RowHammer Mitigation_ , 2021.
  * [44] W. Kim, “A 1.1V 16Gb DDR5 DRAM with Probabilistic-Aggressor Tracking, Refresh-Management Functionality, Per-Row Hammer Tracking, a Multi-Step Precharge, and Core-Bias Modulation for Security and Reliability Enhancement,” in _ISSCC_ , 2023.
  * [45] S. Hong _et al._ , “DSAC: Low-Cost Rowhammer Mitigation Using In-DRAM Stochastic and Approximate Counting Algorithm,” arXiv:2302.03591, 2023.
  * [46] A. Kogler _et al._ , “Half-Double: Hammering From the Next Row Over,” in _USENIX Security_ , 2022.
  * [47] L. Cojocar _et al._ , “Are We Susceptible to Rowhammer? An End-to-End Methodology for Cloud Providers,” in _S &P_, 2020.
  * [48] K. Loughlin _et al._ , “MOESI-Prime: Preventing Coherence-Induced Hammering in Commodity Workloads,” in _ISCA_ , 2022.
  * [49] T. Bennett _et al._ , “Panopticon: A Complete In-DRAM Rowhammer Mitigation,” in _DRAMSec_ , 2021.
  * [50] K. Loughlin _et al._ , “Stop! Hammer Time: Rethinking Our Approach to Rowhammer Mitigations,” in _HotOS_ , 2021.
  * [51] S. Saroiu and A. Wolman, “How to Configure Row-Sampling-Based Rowhammer Defenses,” _DRAMSec_ , 2022.
  * [52] O. Mutlu, “Memory Scaling: A Systems Architecture Perspective,” in _IMW_ , 2013.
  * [53] L. Orosa, “A Deeper Look into RowHammer’s Sensitivities: Experimental Analysis of Real DRAM Chips and Implications on Future Attacks and Defenses,” in _MICRO_ , 2021.
  * [54] A. G. Yağlıkcı _et al._ , “Understanding RowHammer Under Reduced Wordline Voltage: An Experimental Study Using Real DRAM Devices,” in _DSN_ , 2022.
  * [55] H. Luo _et al._ , “RowPress: Amplifying Read Disturbance in Modern DRAM Chips,” in _ISCA_ , 2023.


# Active Inverse Learning in Stackelberg Trajectory Games

Yue Yu, Jacob Levy, Negar Mehr, David Fridovich-Keil, and Ufuk Topcu Y. Yu, J.
Levy, D. Fridovich-Keil, and U. Topcu are with the Oden Institute for
Computational Engineering and Sciences, The University of Texas at Austin,
Austin, TX, 78712, USA (emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>utopcu@utexas.edu). N. Mehr is with the Department of
Aerospace Engineering at the University of Illinois at Urbana-Champaign,
Urbana, IL, 61801, USA (email: negar@illinois.edu).

###### Abstract

Game-theoretic inverse learning is the problem of inferring the players’
objectives from their actions. We formulate an inverse learning problem in a
Stackelberg game between a leader and a follower, where each player’s action
is the trajectory of a dynamical system. We propose an active inverse learning
method for the leader to infer which hypothesis among a finite set of
candidates describes the follower’s objective function. Instead of using
passively observed trajectories like existing methods, the proposed method
actively maximizes the differences in the follower’s trajectories under
different hypotheses to accelerate the leader’s inference. We demonstrate the
proposed method in a receding-horizon repeated trajectory game. Compared with
uniformly random inputs, the leader inputs provided by the proposed method
accelerate the convergence of the probability of different hypotheses
conditioned on the follower’s trajectory by orders of magnitude.

##  I Introduction

Learning to predict human behavior is a critical challenge in human-robot
interaction. It enables robots to customize their strategies in various
applications, including assisted driving [1, 2], traffic management [3, 4],
and, in general, mitigating conflicts in human-in-the-loop robotic systems.

Game-theoretic inverse learning helps robots explain and predict human
behavior in noncooperative interactions [5, 6, 7, 8, 9, 10, 11, 3]. The idea
is to first model humans’ objectives as parameterized functions, then infer
the parameter value such that the corresponding game-theoretic strategies—such
as Nash or Stackelberg equilibrium strategies—match the humans’ actions in a
dataset. Game-theoretic inverse learning is a necessary step in understanding
human-robot interactions [12, 13, 3] and designing incentives for multiagent
systems [14, 15].

The existing game-theoretic inverse learning methods are _passive_ , which can
be data inefficient. In particular, these methods record the dataset of human
actions before and independently of the inference process. Hence some actions
in the recorded dataset can be uninformative for inference purposes, or simply
redundant. As a result, passive inverse learning lacks the data efficiency to
enable rapid inference and support online real-time decision-making.

In contrast to passive inverse learning, active inverse learning helps robots
to infer human intentions in cooperative interactions by actively provoking
informative human actions. For example, when learning objectives that explain
human’s ranking or rating of presented options, active inverse learning
methods first provoke informative human actions and record them in the
dataset, then infer the human’s objective function, and repeat this process if
necessary [16, 17, 18, 19, 20]. These methods ensure that the human’s actions
are informative by maximizing the volume removed from the hypothesis space
[18, 21, 22, 23, 24, 25] or by maximizing the information gain [26, 27, 4, 28,
29, 30]. By integrating dataset updates with inference, active inverse
learning provides practical solutions for inferring human intentions from
limited interactions.

Despite its successes, active inverse learning still requires investigation in
noncooperative interactions. The existing active inverse learning methods rely
on querying humans who volunteer informative responses. In contrast, humans in
noncooperative interactions only take actions that optimize their own
objectives. Therefore, how to provoke informative actions from noncooperative
humans that reveal their objectives is, to our best knowledge, still an open
question.

We formulate an inverse learning problem in a Stackelberg game where a
rational leader, such as a robot, is inferring which hypothesis among finitely
many candidates best explains the behavior of a boundedly rational follower,
such as a human. This problem is particularly relevant in shared autonomy,
e.g., when an autopilot is inferring the type of a newly encountered human
driver. We model each player’s action as the trajectory of a linear time-
invariant system. The follower tracks a linear function of the leader’s
trajectory—similar to how a human driver tracks the trajectory recommended by
an autopilot—using a maximum-entropy linear quadratic regulator—which contains
a parameterized objective function—that models bounded rationality in human
decision-making [3]. The leader determines which hypothesis is most likely
using the probability of each hypothesis conditioned on the follower’s state
trajectory.

We propose an active inverse learning method to provoke informative
trajectories from the follower by optimizing the leader’s inputs. In this
optimization, we maximize the differences in the follower’s trajectory
distributions under different hypotheses. We show that this optimization is a
difference-of-convex program [31], which can be solved efficiently via the
convex-concave procedure [32]. We evaluate the performance of the proposed
method in a receding-horizon repeated trajectory game. Compared with random
inputs, the leader inputs provided by our method accelerate the convergence of
the probability of different hypotheses conditioned on the follower’s
trajectory by orders of magnitude.

Notation: We let $\mathbb{R}$, $\mathbb{R}_{\geq 0}$, and $\mathbb{N}$ denote
the set of real, nonnegative real numbers, and nonnegative integers,
respectively. We let $\mathbb{S}_{\succeq 0}^{n}$ and $\mathbb{S}_{\succ
0}^{n}$ denote the set of $n$ by $n$ symmetric positive semidefinite and
positive definite matrices, respectively. For any $x\in\mathbb{R}^{n}$, we let
$\left\lVert x\right\rVert\coloneqq\sqrt{x^{\top}x}$, $\left\lVert
x\right\rVert_{1}\coloneqq\sum_{i=1}^{n}|x_{i}|$, $\left\lVert
x\right\rVert_{\infty}\coloneqq\max_{1\leq i\leq n}|x_{i}|$, and $\left\lVert
x\right\rVert_{A}^{2}\coloneqq x^{\top}Ax$ for all $A\in\mathbb{S}_{\succeq
0}^{n}$. We let $0_{n}$ denote the $n$-dimensional zero vector; $I_{n}$ and
$0_{n\times n}$ denote the $n$ by $n$ identity and zero matrix, respectively.
We let $\mathcal{N}(\mu,\Sigma)$ denote the Gaussian distribution with mean
$\mu\in\mathbb{R}^{n}$ and variance $\Sigma\in\mathbb{S}_{\succ 0}^{n}$. Given
$n_{1},n_{2}\in\mathbb{N}$, we let $[n_{1},n_{2}]$ denote the set of integers
between $n_{1}$ and $n_{2}$. Given $a_{i}\in\mathbb{R}^{n}$ for all
$i\in\mathbb{N}$, we let
$a_{i:j}\coloneqq\begin{bmatrix}a_{i}^{\top}&a_{i+1}^{\top}&\cdots&a_{j}^{\top}\end{bmatrix}^{\top}$
for all $i<j$, $i,j\in\mathbb{N}$.

##  II Linear quadratic Stackelberg trajectory games

We introduce a Stackelberg game between a rational leader, such as a robot,
and a boundedly rational follower, such as a human with noisy behavior. The
players’ actions are trajectories of stochastic linear time-invariant systems.

###  II-A The dynamics of the players’ systems

We assume that the leader’s state evolves according to the following discrete-
time linear time-invariant dynamics:

$x_{t+1}^{\texttt{L}}=A^{\texttt{L}}x_{t}^{\texttt{L}}+B^{\texttt{L}}u_{t}^{\texttt{L}}+w_{t}^{\texttt{L}}$
(1)

for all $t\in\mathbb{N}$, where
$x_{t}^{\texttt{L}}\in\mathbb{R}^{n_{\texttt{L}}}$,
$u_{t}^{\texttt{L}}\in\mathbb{R}^{m_{\texttt{L}}}$, and
$w_{t}^{\texttt{L}}\in\mathbb{R}^{\texttt{L}}$ are the state, input, and
disturbance of the system at time $t\in\mathbb{N}$, respectively;
$A^{\texttt{L}}\in\mathbb{R}^{n_{\texttt{L}}\times n_{\texttt{L}}}$ and
$B^{\texttt{L}}\in\mathbb{R}^{n_{\texttt{L}}\times m_{\texttt{L}}}$ are the
leader’s system parameters. Equation (1) characterizes the dynamics of many
common robots, such as the kinematics of rovers and drones.

Similarly, the follower’s state evolves according to the following dynamics:

$x_{t+1}^{\texttt{F}}=A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}}$
(2)

for all $t\in\mathbb{N}$, where
$x_{t}^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{L}}}$,
$u_{t}^{\texttt{F}}\in\mathbb{R}^{m_{\texttt{L}}}$, and
$w_{t}^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{L}}}$ denote the state, input,
and disturbance of the system at time $t\in\mathbb{N}$, respectively;
$A^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{L}}\times n_{\texttt{L}}}$ and
$B^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{F}}\times m_{\texttt{F}}}$ are the
follower’s system parameters.

Throughout, we assume that the disturbance in the leader and the follower’s
systems are independent, identically distributed Gaussian vectors, i.e., there
exists $\Omega^{\texttt{L}}\in\mathbb{S}^{n_{\texttt{L}}}_{\succ 0}$ and
$\Omega^{\texttt{F}}\in\mathbb{S}^{n_{\texttt{F}}}_{\succ 0}$ such that, for
any $t\in\mathbb{N}$, we have

$w_{t}^{\texttt{L}}\sim\mathcal{N}(0_{n_{\texttt{L}}},\Omega^{\texttt{L}}),\,w_{t}^{\texttt{F}}\sim\mathcal{N}(0_{n_{\texttt{L}}},\Omega^{\texttt{F}}).$
(3)

###  II-B The players’ objectives

We assume that the follower’s objective is to track a linear function of the
leader’s trajectory. In particular, we let
$M^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{F}}\times n_{\texttt{L}}}$ denote a
matrix that maps the leader’s internal state to an output reference observable
to the follower. Let $x_{0:\tau}^{\texttt{L}}$ denote a leader trajectory of
length $\tau\in\mathbb{N}$. The follower’s objective is to simultaneously
track the corresponding output trajectory
$\\{M^{\texttt{F}}x^{\texttt{L}}_{0},M^{\texttt{F}}x^{\texttt{L}}_{1},\ldots,M^{\texttt{F}}x^{\texttt{L}}_{\tau}\\}$
and minimize its input efforts.

We assume that the follower is boundedly rational and chooses its input
according to the maximum entropy principle, which states that the distribution
of $u_{t}^{\texttt{F}}$ conditioned on $x_{t}^{\texttt{F}}$ is Gaussian, i.e.,
$\mu_{t}^{\texttt{F}}|x_{t}^{\texttt{F}}\sim\mathcal{N}(\mu_{t},\Sigma_{t})$
for some $\mu_{t}\in\mathbb{R}^{n_{\texttt{F}}}$ and
$\Sigma_{t}\in\mathbb{R}^{n_{\texttt{F}}}$ [3]. In particular,
$(\mu_{0:\tau-1},\Sigma_{0:\tau-1})$ is optimal for the following stochastic
trajectory optimization problem:

$\begin{array}[]{ll}\underset{\mu_{0:\tau-1},\Sigma_{0:\tau-1}}{\mbox{minimize}}&\sum_{t=0}^{\tau}\mathds{E}\left[\frac{1}{2}\left\lVert
x_{t}^{\texttt{F}}-M^{\texttt{F}}x_{t}^{\texttt{L}}\right\rVert_{Q^{\texttt{F}}}^{2}\right]\\\
&+\frac{1}{2}\sum_{t=0}^{\tau-1}\left(\mathds{E}\left[\left\lVert
u_{t}^{\texttt{F}}\right\rVert_{R^{\texttt{F}}}^{2}\right]-\log\det\Sigma_{t}\right)\\\
\mbox{subject
to}&x_{t+1}^{\texttt{F}}=A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}},\,x_{0}^{\texttt{F}}=\hat{x}_{0}^{\texttt{F}},\\\
&u_{t}^{\texttt{F}}|x_{t}^{\texttt{F}}\sim\mathcal{N}(\mu_{t},\Sigma_{t}),\,w_{t}^{\texttt{F}}\sim\mathcal{N}(0_{n_{\texttt{F}}},\Omega^{\texttt{F}}),\\\
&t\in[0,\tau-1],\end{array}$ (4)

where $\hat{x}^{\texttt{F}}_{0}\in\mathbb{R}^{\texttt{F}}$ is the initial
state of the follower’s system, $\mathds{E}[\cdot]$ denotes the expectation;
$Q^{\texttt{F}}\in\mathbb{S}^{n}_{\succeq 0}$, and
$R^{\texttt{F}}\in\mathbb{S}^{n}_{\succ 0}$ are the follower’s cost
parameters. The objective function in optimization (4) captures boundedly
rational human decisions: it is noisy but centers around a cost-minimizing
rational decision.

The following proposition provides a closed-form formula for the solution of
optimization (4).

######  Proposition 1.

Let

$\displaystyle
P^{\texttt{F}}_{\tau}=Q^{\texttt{F}},\,P^{\texttt{F}}=Q^{\texttt{F}}+(A^{\texttt{F}})^{\top}P^{\texttt{F}}_{t+1}E^{\texttt{F}}_{t},$
(5a) $\displaystyle
F^{\texttt{F}}_{t}=B^{\texttt{F}}(R+(B^{\texttt{F}})^{\top}P^{\texttt{F}}_{t+1}B^{\texttt{F}})^{-1}(B^{\texttt{F}})^{\top},$
(5b) $\displaystyle
E^{\texttt{F}}_{t}=A^{\texttt{F}}-F^{\texttt{F}}_{t}P^{\texttt{F}}_{t+1}A^{\texttt{F}},$
(5c) $\displaystyle
q_{\tau}^{\texttt{F}}=-Q^{\texttt{F}}M^{\texttt{F}}x_{\tau}^{\texttt{L}},\,q_{t}^{\texttt{F}}=(E^{\texttt{F}}_{t})^{\top}q_{t+1}^{\texttt{F}}-Q^{\texttt{F}}M^{\texttt{F}}x_{t}^{\texttt{L}},$
(5d)

for all $t\in[0,\tau-1]$. Given $x^{\texttt{L}}_{0:\tau}$,
$(\mu_{0:\tau-1},\Sigma_{0:\tau-1})$ is optimal for optimization (4) if and
only if

$\displaystyle\Sigma_{t}$
$\displaystyle=(R^{\texttt{F}}+(B^{\texttt{F}})^{\top}P^{\texttt{F}}_{t+1}B^{\texttt{F}})^{-1},$
(6a) $\displaystyle\mu_{t}$
$\displaystyle=-\Sigma_{t}(B^{\texttt{F}})^{\top}(P^{\texttt{F}}_{t+1}A^{\texttt{F}}x_{t}^{\texttt{F}}+q_{t+1}^{\texttt{F}}).$
(6b)

for all $t\in[0,\tau-1]$. Furthermore, if the constraints in (4) hold, then
$x_{t}^{\texttt{F}}\sim\mathcal{N}(\xi_{t},\Lambda_{t})$ for all
$t\in[0,\tau]$, where

$\displaystyle\xi_{t+1}$
$\displaystyle=E^{\texttt{F}}_{t}\xi_{t}-F^{\texttt{F}}_{t}q_{t+1}^{\texttt{F}},$
(7a) $\displaystyle\Lambda_{t+1}$
$\displaystyle=E^{\texttt{F}}_{t}\Lambda_{t}(E^{\texttt{F}}_{t})^{\top}+F^{\texttt{F}}_{t}+\Omega^{\texttt{F}},$
(7b)

for all $t\in[0,\tau-1]$, with $\xi_{0}=\hat{x}^{\texttt{F}}_{0}$ and
$\Lambda_{0}=0_{n_{\texttt{F}}\times n_{\texttt{F}}}$..

###### Proof.

See Appendix. ∎

The leader’s objective is to minimize a cost function that jointly depends on
the expected follower’s trajectory and the leader’s trajectory. To this end,
we assume that the leader acts rationally and chooses its trajectory
$x^{\texttt{L}}_{0:\tau}$ as a solution to the following trajectory
optimization problem:

$\begin{array}[]{ll}\underset{u_{0:\tau-1}}{\mbox{minimize}}&\mathds{E}[f(x^{\texttt{L}}_{0:\tau},x^{\texttt{F}}_{0:\tau})]+g(u^{\texttt{L}}_{0:\tau})\\\
\mbox{subject
to}&x_{t+1}^{\texttt{L}}=A^{\texttt{L}}x_{t}^{\texttt{L}}+B^{\texttt{L}}u_{t}^{\texttt{L}}+w_{t}^{\texttt{L}},\,x_{0}^{\texttt{L}}=\hat{x}^{\texttt{L}}_{0},\\\
&x_{t+1}^{\texttt{F}}=A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}},\,x_{0}^{\texttt{F}}=\hat{x}_{0}^{\texttt{F}},\\\
&w_{t}^{\texttt{L}}\sim\mathcal{N}(0_{n_{\texttt{L}}},\Omega^{\texttt{L}}),\,w_{t}^{\texttt{F}}\sim\mathcal{N}(0_{n_{\texttt{F}}},\Omega^{\texttt{F}}),\\\
&u_{t}\in\mathbb{U},\,u_{t}^{\texttt{F}}|x_{t}^{\texttt{F}}\sim\mathcal{N}(\mu_{t},\Sigma_{t}),\,t\in[0,\tau-1],\\\
&(\mu_{0:\tau-1},\Sigma_{0:\tau-1})\text{ is optimal for \eqref{opt:
f-lqr},}\end{array}$ (8)

where $\hat{x}^{\texttt{L}}_{0}\in\mathbb{R}^{n_{\texttt{L}}}$ is the initial
state of the leader’s system, $\mathbb{U}\subset\mathbb{R}^{m_{\texttt{F}}}$
is the set of feasible leader inputs at each time. Furthermore,
$f:\mathbb{R}^{(\tau+1)n_{\texttt{L}}}\times\mathbb{R}^{(\tau+1)n_{\texttt{L}}}\to\mathbb{R}$
is the leader’s cost function that jointly depends on the leader’s state
trajectory $x^{\texttt{L}}_{0:\tau}$ and the follower’s state trajectory
$x^{\texttt{F}}_{0:\tau}$; $g:\mathbb{R}^{\tau m_{\texttt{L}}}\to\mathbb{R}$
is a cost function that only depends on the leader’s input trajectory. By
choosing different functions for $f$ and $g$, optimization (8) achieves
different trade-offs between optimizing the leader and the follower’s
trajectory.

Problem (8) is a Stackelberg game, also known as a _bilevel optimization_. See
[33] and reference therein for a detailed discussion on bilevel optimization.

##  III Active inverse learning via difference maximization

Given the Stackelberg trajectory game introduced in Section II, we now
consider the case where the leader does not know the parameter tuple
$(Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})$ in the follower’s objective,
except that it is one of finitely many candidates. In other words, the leader
knows that there exist $Q^{1},\ldots,Q^{d}\in\mathbb{R}^{n^{\texttt{F}}\times
n^{\texttt{F}}}$, $R^{1},\ldots,R^{d}\in\mathbb{R}^{m^{\texttt{F}}\times
m^{\texttt{F}}}$, and $M^{1},\ldots,M^{d}\in\mathbb{R}^{n^{\texttt{F}}\times
n^{\texttt{L}}}$ such that

$(Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})=(Q^{i},R^{i},M^{i})$ (9)

for some $i\in[1,d]$. This case arises, for example, when a robot already
learned different types of human behavior offline but needs to determine the
type of a newly encountered human via online interaction. In the following, we
let
$\theta^{\texttt{F}}\coloneqq(Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})$
and $\theta^{i}\coloneqq(Q^{i},R^{i},M^{i})$ for all $i\in[1,d]$. We say that
_hypothesis $i$ is true_ if (9) holds.

Based on a prior probability distribution of all hypotheses that gives the
value of $\mathds{P}(\theta^{\texttt{F}}=\theta^{i}|x_{0}^{\texttt{F}})$ for
all $i\in[1,d]$ and the follower’s trajectory $x^{\texttt{F}}_{1:\tau}$, the
leader can infer whether hypothesis $i$ is more likely than hypothesis $j$ to
be true by computing the following ratio:

$\frac{\mathds{P}(\theta^{\texttt{F}}=\theta^{i}|x^{\texttt{F}}_{0:\tau})}{\mathds{P}(\theta^{\texttt{F}}=\theta^{j}|x^{\texttt{F}}_{0:\tau})}=\frac{\mathds{P}(\theta^{\texttt{F}}=\theta^{i}|x^{\texttt{F}}_{0})\mathds{P}(x^{\texttt{F}}_{1:\tau}|\theta^{\texttt{F}}=\theta^{i})}{\mathds{P}(\theta^{\texttt{F}}=\theta^{j}|x^{\texttt{F}}_{0})\mathds{P}(x^{\texttt{F}}_{1:\tau}|\theta^{\texttt{F}}=\theta^{j})}$
(10)

The ratio in (10) being bigger than one implies that trajectory
$x^{\texttt{F}}_{0:\tau}$ is more likely to occur under hypothesis $i$ rather
than hypothesis $j$, and vice versa.

However, observing the follower’s trajectory can be uninformative for the
inference above if the trajectories under different hypotheses are similar.
For example, suppose that

$\mathds{P}(x^{\texttt{F}}_{1:\tau}|\theta^{\texttt{F}}=\theta^{i})\approx\mathds{P}(x^{\texttt{F}}_{1:\tau}|\theta^{\texttt{F}}=\theta^{j})$
(11)

for some $i\neq j$, then (10) implies that
$\frac{\mathds{P}(\theta^{\texttt{F}}=\theta^{i}|x^{\texttt{F}}_{0:\tau})}{\mathds{P}(\theta^{\texttt{F}}=\theta^{j}|x^{\texttt{F}}_{0:\tau})}\approx\frac{\mathds{P}(\theta^{\texttt{F}}=\theta^{i}|x^{\texttt{F}}_{0})}{\mathds{P}(\theta^{\texttt{F}}=\theta^{j}|x^{\texttt{F}}_{0})}$.
In other words, observing the follower’s ongoing trajectory
$x^{\texttt{F}}_{1:\tau}$ does not help the leader distinguish hypothesis $i$
from $j$. In the following, we discuss how the leader can actively avoid the
scenarios where (11) happens by making the follower’s trajectories under
different hypotheses as different as possible.

###  III-A The follower’s trajectories under different hypotheses

To avoid the scenarios where (11) happens, it suffices to make the follower’s
trajectory distributions under different hypotheses as different as possible.
To this end, we first take a closer look at the follower’s trajectory.
Proposition 1 shows that the follower’s state at each time is a Gaussian
random variable. Particularly, let

$\displaystyle E^{i}_{t}=A^{\texttt{F}}-F^{i}_{t}P^{i}_{t+1}A^{\texttt{F}},$
(12a) $\displaystyle
F^{i}_{t}=B^{\texttt{F}}(R^{\texttt{F}}+(B^{\texttt{F}})^{\top}P^{i}_{t+1}B^{\texttt{F}})^{-1}(B^{\texttt{F}})^{\top},$
(12b) $\displaystyle
P_{\tau}^{i}=Q^{i},\,P^{i}_{t}=Q^{i}+(A^{\texttt{F}})^{\top}P^{i}_{t+1}E^{i}_{t},$
(12c) $\displaystyle\Lambda_{0}^{i}=0_{n_{\texttt{F}}\times
n_{\texttt{F}}},\,\Lambda_{t+1}^{i}=E^{i}_{t}\Lambda_{t}^{i}(E^{i}_{t})^{\top}+F^{i}_{t}+\Omega^{\texttt{F}},$
(12d) $\displaystyle
q_{\tau}^{i}=-Q^{i}M^{i}x_{\tau}^{\texttt{L}},\,q_{t}^{i}=(E^{i}_{t})^{\top}q_{t+1}^{i}-Q^{i}M^{i}x_{t}^{\texttt{L}},$
(12e)
$\displaystyle\xi_{0}^{i}=\hat{x}^{\texttt{F}}_{0},\,\xi_{t+1}^{i}=E^{i}_{t}\xi_{t}^{i}+F^{i}_{t}q_{t+1}^{i},$
(12f)

for all $t\in[0,\tau-1]$. Proposition 1 implies that, if hypothesis $i$ is
true, i.e., $\theta^{\texttt{F}}=\theta^{i}$, then

$x^{\texttt{F}}_{t}\sim\mathcal{G}_{t}^{i}\coloneqq\mathcal{N}(\xi^{i}_{t},\Lambda^{i}_{t}).$
(13)

To measure the differences between the trajectory distribution under different
hypotheses, we introduce a distance function. To this end, let

$\mathbb{D}\coloneqq\\{(i,j)|i<j,\,i,j\in[1,d]\\}.$ (14)

A popular measure of the difference between two Gaussian distributions is the
_KL-divergence_. Given $(i,j)\in\mathbb{D}$ and $t\in[1,\tau]$, let
$\mathcal{G}_{t}^{i}$ and $\mathcal{G}_{t}^{j}$ be defined as in (13). The KL-
divergence from $\mathcal{G}^{i}_{t}$ to $\mathcal{G}^{j}_{t}$ is as follows:

$\displaystyle D_{KL}(\mathcal{G}^{i}_{t}||\mathcal{G}^{j}_{t})\coloneqq$
$\displaystyle\textstyle\frac{1}{2}\left\lVert\xi_{t}^{i}-\xi_{t}^{j}\right\rVert^{2}_{(\Lambda^{j}_{t})^{-1}}-\frac{(\tau+1)n_{\texttt{F}}}{2}$
(15)
$\displaystyle\textstyle+\frac{1}{2}\log\left(\frac{\det\Lambda_{t}^{j}}{\det\Lambda_{t}^{i}}\right)+\mathop{\rm
tr}((\Lambda_{t}^{j})^{-1}\Lambda_{t}^{i}).$

Notice that, since $\Omega^{\texttt{F}}\in\mathbb{S}_{\succ
0}^{n_{\texttt{F}}}$, (12) implies that $\Lambda_{t}^{i}\in\mathbb{S}_{\succ
0}^{n_{\texttt{F}}}$ for all $t\in[1,\tau]$ and $k\in[1,d]$. However, KL
divergence is not symmetric, i.e.,
$D_{KL}(\mathcal{G}^{i}_{t}||\mathcal{G}^{j}_{t})\neq
D_{KL}(\mathcal{G}^{j}_{t}||\mathcal{G}^{i}_{t})$. To define a symmetric
distance function, we propose the following function

$D(\mathcal{G}^{i}_{t},\mathcal{G}^{j}_{t})\coloneqq\left\lVert\xi^{i}_{t}-\xi^{j}_{t}\right\rVert^{2}_{(\Lambda^{i}_{t})^{-1}+(\Lambda^{j}_{t})^{-1}}$
(16)

for all $t\in[1,\tau]$ and $(i,j)\in\mathbb{D}$. The intuition behind this
distance function is to first evaluate (up to a constant of $2$, for the
convenience of notation) the sum of
$D_{KL}(\mathcal{G}^{i}_{t}||\mathcal{G}^{j}_{t})$ and
$D_{KL}(\mathcal{G}^{j}_{t}||\mathcal{G}^{i}_{t})$, then remove the terms that
are independent of $\xi^{i}_{t}$ and $\xi^{j}_{t}$, which are, as suggested by
(12), independent of the leader’s trajectory. Later, we use this function to
optimize the leader’s inputs.

###  III-B Maximizing the worst-case pairwise distance

To avoid the scenarios where (11) happens, we need to maximize the value of
the distance function in (16) for any $(i,j)\in\mathbb{D}$. To this end,
define the following _worst-case distance function_ , which evaluates the
minimum value of function (16) among all $(i,j)\in\mathbb{D}$:

$\displaystyle\textstyle\underset{(i,j)\in\mathbb{D}}{\min}\left\\{\sum_{t=1}^{\tau}\left\lVert\xi_{t}^{i}-\xi_{t}^{i}\right\rVert_{(\Lambda^{i}_{t})^{-1}+(\Lambda^{j}_{t})^{-1}}^{2}\right\\}$
(17)
$\displaystyle=\textstyle\sum\limits_{(i,j)\in\mathbb{D}}\sum_{t=1}^{\tau}\left\lVert\xi_{t}^{i}-\xi_{t}^{i}\right\rVert_{(\Lambda^{i}_{t})^{-1}+(\Lambda^{j}_{t})^{-1}}^{2}$
$\displaystyle\textstyle-\underset{(i,j)\in\mathbb{D}}{\max}\left\\{\sum\limits_{(k,l)\in\mathbb{D}\setminus\\{(i,j)\\}}\sum_{t=1}^{\tau}\left\lVert\xi_{t}^{k}-\xi_{t}^{l}\right\rVert_{(\Lambda^{k})^{-1}_{t}+(\Lambda^{l})^{-1}_{t}}^{2}\right\\}.$

The second step in (17) uses the fact that, given any
$\alpha_{1},\ldots,\alpha_{n}\in\mathbb{R}$, we have

$\textstyle\min\limits_{i\in[1,n]}\alpha_{i}=\sum\limits_{i\in[1,n]}\alpha_{i}-\max\limits_{i\in[1,n]}\sum\limits_{j\in[1,n],j\neq
i}\alpha_{j}.$

Notice that the distance in (17) does not include the terms for $t=0$ since,
due to (12), $\xi_{0}^{i}=\xi_{0}^{j}$ for all $(i,j)\in\mathbb{D}$.

$\begin{array}[]{ll}\underset{s,u_{0:\tau-1}^{\texttt{L}}}{\mbox{minimize}}&s-\sum_{(i,j)\in\mathbb{D}}\sum_{t=0}^{\tau}\left\lVert\xi_{t}^{i}-\xi_{t}^{j}\right\rVert_{(\Lambda^{i}_{t})^{-1}+(\Lambda^{j}_{t})^{-1}}^{2}+g(u_{0:\tau-1})\\\
\mbox{subject
to}&\eta_{t+1}^{\texttt{L}}=A^{\texttt{L}}\eta_{t}^{\texttt{L}}+B^{\texttt{L}}u_{t}^{\texttt{L}},\,\eta_{0}^{\texttt{L}}=\hat{x}^{\texttt{L}}_{0},\\\
&q_{t}^{i}=(E_{t}^{i})^{\top}q_{t+1}^{i}-Q^{i}M^{i}\eta_{t},\,q_{\tau}^{i}=-Q^{i}M^{i}\eta_{\tau},\,\xi_{t+1}^{i}=E_{t}^{i}\xi_{t}^{i}-F_{t}^{i}q_{t+1}^{i},\,\xi_{0}^{i}=\hat{x}_{0}^{\texttt{F}},\\\
&\sum_{(k,l)\in\mathbb{D}\setminus\\{(i,j)\\}}\sum_{t=1}^{\tau}\left\lVert\xi_{t}^{k}-\xi_{t}^{l}\right\rVert_{(\Lambda^{k})^{-1}_{t}+(\Lambda^{l})^{-1}_{t}}^{2}\leq
s,\,\forall t\in[0,\tau-1],\,i\in[1,d],\,(i,j)\in\mathbb{D}.\end{array}$ (18)

Based on the worst-case distance in (17), we propose to optimize the leader’s
input trajectory $u^{\texttt{L}}_{0:\tau-1}$ via solving optimization (18)
(see next page) instead of optimization (8), where $E_{t}^{i},F_{t}^{i}$ and
$\Lambda_{t}^{i}$ are given by (12). The idea of optimization (18) is to first
approximate the leader’s state trajectory $x^{\texttt{L}}_{0:\tau}$ with its
expectation, denoted by $\eta_{0:\tau}$, which satisfies the averaged dynamics
$\eta_{t+1}=A^{\texttt{L}}\eta_{t}+B^{\texttt{L}}u^{\texttt{L}}_{t}$. This
approximation replaces the disturbance term $w_{t}^{\texttt{L}}$ in (8) with
its most probable estimation of its distribution
$\mathcal{N}(0_{n_{\texttt{L}}},\Omega^{\texttt{L}})$, given by
$w_{t}^{\texttt{L}}=0_{n_{\texttt{L}}}$. In addition, optimization (18)
replaces the $\mathds{E}[f(x^{\texttt{L}}_{0:\tau},x^{\texttt{F}}_{0:\tau})]$
term in (8) with the negative of the worst-case distance in (17). In
particular, the constraints in (18) imply that

$\textstyle\underset{(i,j)\in\mathbb{D}}{\max}\left\\{\sum\limits_{(k,l)\in\mathbb{D}\setminus\\{(i,j)\\}}\sum\limits_{t=1}^{\tau}\left\lVert\xi_{t}^{k}-\xi_{t}^{l}\right\rVert_{(\Lambda^{k})^{-1}_{t}+(\Lambda^{l})^{-1}_{t}}^{2}\right\\}\leq
s.$

Since the objective function in (18) is minimizing the value of $s$, the above
inequality holds as an equality at optimality. Hence the objective function in
(18) is equivalent to the one in (8) except that the
$\mathds{E}[f(x^{\texttt{L}}_{0:\tau},x^{\texttt{F}}_{0:\tau})]$ term in (8)
is replaced by the negative of the worst-case distance in (17). The idea of
this replacement is to maximize the worst-case distance in (17), which ensures
that the distance in (16) is large for any $(i,j)\in\mathbb{D}$.

Optimization (18) is a difference-of-convex program: all of its constraints
are convex, but its objective function is the difference between two convex
functions [31]. A popular solution method for difference-of-convex programs is
the _convex-concave procedure_ , which guarantees global convergence to a
stationary point [34], and provides locally optimal solutions in practice
[32].

##  IV Numerical Experiments

We empirically demonstrate our results using a receding-horizon repeated
trajectory game between a boundedly rational follower that controls one ground
rover and a rational leader that controls multiple ground rovers. The leader
is inferring which leading rover the follower is following. At each time step,
the players play a Stackelberg trajectory game and implement only the first
step of theire respective input trajectories.

We define the game parameters as follows. We model the dynamics of the
following rover using an instance of (1), where
$A^{\texttt{F}}=\exp\left(\delta\begin{bmatrix}0_{2\times 2}&I_{2}\\\
0_{2\times 2}&0_{2\times 2}\end{bmatrix}\right)$,
$B^{\texttt{F}}=\int_{0}^{\delta}\exp\left(t\begin{bmatrix}0_{2\times
2}&I_{2}\\\ 0_{2\times 2}&0_{2\times
2}\end{bmatrix}\right)\mathrm{d}t\begin{bmatrix}0_{2\times 2}\\\
I_{2}\end{bmatrix}$, $\Omega^{\texttt{F}}=\frac{1}{1000}I_{4}$, and
$\delta=0.2$ is the discretization step size. For the leader, we model the
joint dynamics of $d\in\mathbb{N}$ ground rovers using the joint dynamics of
$d$ double-integrators, where we let $A^{\texttt{L}}=I_{d}\otimes A$,
$B^{\texttt{L}}=I_{d}\otimes B$, and
$\Omega^{\texttt{L}}=\frac{1}{1000}I_{4d\times 4d}$. For the follower’s
trajectory optimization in (4), we let $Q^{i}=\mathop{\rm
diag}(\begin{bmatrix}1&1&0&0\end{bmatrix})$, $R^{i}=\frac{1}{100}I_{2}$, and
$M^{i}=\begin{bmatrix}0_{4\times 4(i-1)}&I_{4}&0_{4\times
4(d-i)}\end{bmatrix}$ for all $i\in[1,d]$. Without loss of generality, we
assume $(Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})=(Q^{1},R^{1},M^{1})$.
For the leader’s trajectory optimization in (8), we let
$\mathbb{U}\coloneqq\\{u\in\mathbb{R}^{2d}|\left\lVert
u\right\rVert_{\infty}\leq 2\\}$, and
$g(u^{\texttt{L}}_{0:\tau-1})\sum_{t=1}^{\tau-2}\left\lVert
u^{\texttt{L}}_{t+1}-u^{\texttt{L}}_{t}\right\rVert^{2}$.

$-4$$0$$4$$-4$$0$$4$horizontal positionvertical position (a)

$-4$$0$$4$$-4$$0$$4$horizontal positionvertical position (b)

Figure 1: The position trajectories of the leader’s rovers, where different
rover’s trajectories are marked by different colors.

We demonstrate the proposed learning methods using the simulation of a
receding-horizon repeated trajectory game. At time $t\delta$ for some
$t\in\mathbb{N}$, the leader first observes its current state
$\overline{x}^{\texttt{L}}_{t}$ and the follower’s current state
$\overline{x}^{\texttt{F}}_{t}$, then solves optimization (18) with
$\hat{x}_{0}^{\texttt{L}}=\overline{x}^{\texttt{L}}_{t}$ and
$\hat{x}^{\texttt{F}}_{0}=\overline{x}^{\texttt{F}}_{t}$ to obtain the optimal
input sequence $u^{\texttt{L}}_{0:\tau-1}$. Next, the leader simulates a state
trajectory $x^{\texttt{L}}_{0:\tau-1}$ according to (1) and shares it with the
follower, then applies $u^{\texttt{L}}_{0}$. Meanwhile, at time $t\delta$, the
follower observes its current state $\hat{x}_{t}^{\texttt{F}}$ and receives
the leader’s simulated trajectory $x_{0:\tau}^{\texttt{L}}$. Next the follower
solves optimization (4) with
$\hat{x}^{\texttt{F}}_{0}=\overline{x}^{\texttt{F}}_{t}$ and obtain the
optimal mean and covariance sequences $(\mu_{0:\tau-1},\Sigma_{0:\tau-1})$,
and finally samples $u_{0}^{\texttt{F}}\sim\mathcal{N}(\mu_{0},\Sigma_{0})$
and applies $u_{0}^{\texttt{F}}$ to its system.

We simulate the players’ trajectories in this receding-horizon repeated
trajectory game, where we solve the leader’s trajectory optimization (18)
using the convex-concave procedure [32]. Fig. 1 shows the position
trajectories of the leader’s rovers when $d=3$ and $d=5$. We can see that, to
make the follower’s trajectories under different hypotheses as different as
possible, optimization (18) ensures that different leading rovers are moving
in different directions.

We further showcase the advantage of the proposed method in terms of
distinguishing different hypotheses. To this end, we let
$p^{\star}=\begin{bmatrix}1&0&\cdots&0\end{bmatrix}^{\top}\in\mathbb{R}^{d}$
denote the ground truth probability of all hypotheses (note that we let
$(Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})=(Q^{1},R^{1},M^{1})$). In
addition, we let $p^{t}$ denote the $d$-dimensional vector such that

$p_{i}^{t}\coloneqq\mathds{P}((Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})=(Q^{i},R^{i},M^{i})|\overline{x}^{\texttt{F}}_{0:t})$
(19)

for all $i\in[1,d]$, where we let
$\mathds{P}((Q^{\texttt{F}},R^{\texttt{F}},M^{\texttt{F}})=(Q^{i},R^{i},M^{i})|\overline{x}^{\texttt{F}}_{0})\coloneqq\frac{1}{d}$
for all $i\in[1,d]$, i.e., we choose the uniform distribution as the leader’s
prior distribution over all hypotheses given the follower’s initial state.
Notice that one can compute $p^{t}$ recursively using the Bayes rule. Fig. 2
shows the time history of the $\ell_{1}$-norm distance between $p^{t}$ and
$p^{\star}$, and compare the results where the leader uses, instead of the
inputs optimal for optimization (18), independent and identically distributed
input sampled from the uniform distribution over $\mathbb{U}$. The results in
Fig. 2 show that, when compared with uniformly random inputs, the proposed
method provide leader inputs that reduce the difference between $p^{t}$ and
$p^{\star}$ by orders of magnitudes.

$0$$2$$4$$6$$8$$10$$10^{-2}$$10^{-1}$$10^{0}$Time steps $t$$\left\lVert
p^{t}-p^{\star}\right\rVert_{1}$ (a) $d=3$.

$0$$2$$4$$6$$8$$10$$10^{-2}$$10^{-1}$$10^{0}$Time step $t$$\left\lVert
p^{t}-p^{\star}\right\rVert_{1}$Proposed inputRandom input (b) $d=5$.

Figure 2: The comparison of the convergence of $p^{t}$ when the leader obtains
its input by solving optimization 18 versus sampling uniformly in set
$\mathbb{U}$. The solid lines show the median over 100 simulations, while the
boundaries of the colored areas mark the corresponding first and third
quartiles.

##  V Conclusion

We formulated an inverse learning problem in a Stackelberg trajectory game,
where the leader is inferring the type of the follower’s cost function by
observing its trajectories. We proposed an active inverse learning method to
accelerate the leader inference by making the follower’s trajectories under
different hypotheses as different as possible. This method accelerates the
convergence of the probability of different hypotheses by orders of magnitude
when compared against random inputs.

However, the current work still has limitations. For example, it considers
neither nonlinear dynamics nor constraints for input limits and collision
avoidance in the players’ trajectory optimization. In addition, it ignores the
possibility of deceptive actions of the follower. In future work, we plan to
address these limitations and develop information-gathering strategies in
general Bayesian games.

## APPENDIX

### Proof of Proposition 1

Given $y\in\mathbb{R}^{n_{\texttt{F}}}$ and $t\in[0,\tau]$, let

$\displaystyle\psi_{t}(y,\mu_{t:\tau},\Sigma_{t:\tau})$ (20)
$\displaystyle\coloneqq\textstyle\sum_{j=t}^{\tau}\mathds{E}\left[\frac{1}{2}\left\lVert
x_{j}^{\texttt{F}}-M^{\texttt{F}}x_{j}^{\texttt{L}}\right\rVert_{Q^{\texttt{F}}}^{2}|x_{t}^{\texttt{F}}=y\right]$
$\displaystyle\textstyle+\frac{1}{2}\sum_{j=t}^{\tau-1}\left(\mathds{E}\left[\left\lVert
u_{j}^{\texttt{F}}\right\rVert_{R^{\texttt{F}}}^{2}|x_{t}^{\texttt{F}}=y\right]\textstyle-\log\det\Sigma_{j}\right).$

where
$x_{j+1}^{\texttt{F}}=A^{\texttt{F}}x_{j}^{\texttt{F}}+B^{\texttt{F}}u_{j}^{\texttt{F}}$
and $u_{j}^{\texttt{F}}\sim\mathcal{N}(\mu_{j},\Sigma_{j})$. Furthermore, let

$V_{t}(y)\coloneqq\min_{\mu_{t:\tau-1},\Sigma_{t:\tau-1}}\psi_{t}(y,\mu_{t:\tau},\Sigma_{t:\tau})$
(21)

for all $t\in[0,\tau]$. Then one can verify that the optimal value of
optimization (4) is $V(\hat{x}_{0}^{\texttt{F}})$. In addition, we can show
that $V_{\tau}(y)=\frac{1}{2}y^{\top}Q^{\texttt{F}}y-\langle
Q^{\texttt{F}}M^{\texttt{F}}x_{\tau}^{\texttt{L}},y\rangle+\frac{1}{2}\left\lVert
M^{\texttt{F}}x_{\tau}^{\texttt{L}}\right\rVert^{2}_{Q^{\texttt{F}}}$, i.e.,
$V_{\tau}(y)$ is a quadratic function of $y$. Suppose that $V_{t+1}(y)$ is a
quadratic function of $y$, i.e., there exists
$P_{t+1}^{\texttt{F}}\in\mathbb{R}^{n_{\texttt{F}}\times n_{\texttt{F}}}$,
$q_{t+1}^{\texttt{F}}\in\mathbb{R}^{\texttt{F}}$, and
$\nu_{t+1}^{\texttt{F}}\in\mathbb{R}$, such that

$\textstyle V_{t+1}(y)=\frac{1}{2}y^{\top}P_{t+1}^{\texttt{F}}y+\langle
q_{t+1}^{\texttt{F}},y\rangle+\nu^{\texttt{F}}_{t+1}.$ (22)

Then (21) and the principle of dynamic programming together imply that

$\displaystyle V_{t}(y)$ (23)
$\displaystyle=\min_{\mu_{t},\Sigma_{t}}\textstyle\mathds{E}\left[\frac{1}{2}\left\lVert
u_{t}^{\texttt{F}}\right\rVert_{R^{\texttt{F}}}^{2}+V_{t+1}(A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}})|x_{t}^{\texttt{F}}=y\right]$
$\displaystyle\textstyle+\frac{1}{2}\left\lVert
y-M^{\texttt{F}}x_{t}^{\texttt{F}}\right\rVert^{2}_{Q^{\texttt{F}}}-\frac{1}{2}\log\det\Sigma_{t}$

where
$u_{t}^{\texttt{F}}|x_{t}^{\texttt{F}}\sim\mathcal{N}(\mu_{t},\Sigma_{t})$.
Observe that

$\displaystyle\mathds{E}[\left\lVert
u_{t}^{\texttt{F}}\right\rVert_{R^{\texttt{F}}}^{2}|x_{t}^{\texttt{F}}=y]$
(24) $\displaystyle=\mu_{t}^{\top}R^{\texttt{F}}\mu_{t}+\mathds{E}[\mathop{\rm
tr}((u_{t}^{\texttt{F}}-\mu_{t})(u_{t}^{\texttt{F}}-\mu_{t})^{\top}R^{\texttt{F}})|x_{t}^{\texttt{F}}=y]$
$\displaystyle=\mu_{t}^{\top}R^{\texttt{F}}\mu_{t}+\mathop{\rm
tr}(\Sigma_{t}R^{\texttt{F}}).$

In addition, by using (22) we can show that

$\displaystyle\mathds{E}[V_{t+1}(A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}})|x_{t}^{\texttt{F}}=y]$
(25)
$\displaystyle=\textstyle\frac{1}{2}(A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t})^{\top}P_{t+1}^{\texttt{F}}(A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t})$
$\displaystyle+\mathds{E}[(A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}\mu_{t})^{\top}P_{t+1}^{\texttt{F}}B^{\texttt{F}}(u_{t}^{\texttt{F}}-\mu_{t})|x_{t}^{\texttt{F}}=y]$
$\displaystyle\textstyle+\frac{1}{2}\mathds{E}[(B^{\texttt{F}}(u_{t}^{\texttt{F}}-\mu_{t}))^{\top}P_{t+1}^{\texttt{F}}B^{\texttt{F}}(u_{t}-\mu_{t})|x_{t}^{\texttt{F}}=y]$
$\displaystyle+\langle
q_{t+1}^{\texttt{F}},A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t}\rangle+\frac{1}{2}\mathds{E}[\mathop{\rm
tr}(w_{t}^{\texttt{F}}(w_{t}^{\texttt{F}})^{\top}P_{t+1})]+\nu_{t+1}^{\texttt{F}}$
$\displaystyle=\textstyle\frac{1}{2}(A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t})^{\top}P_{t+1}^{\texttt{F}}(A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t})+\frac{1}{2}\mathop{\rm
tr}(\Omega^{\texttt{F}}P_{t+1})$
$\displaystyle\textstyle+\frac{1}{2}\mathop{\rm
tr}(\Sigma_{t}(B^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}B^{\texttt{F}})+\langle
q_{t+1}^{\texttt{F}},A^{\texttt{F}}y+B^{\texttt{F}}\mu_{t}\rangle+\nu_{t+1}^{\texttt{F}}.$

Substituting (25) and (24) into (23) gives

$\displaystyle V_{t}(y)$ (26)
$\displaystyle=\textstyle\frac{1}{2}y^{\top}(Q^{\texttt{F}}+(A^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}A^{\texttt{F}})y+\langle
A^{\top}q_{t+1}^{\texttt{F}}-Q^{\texttt{F}}M^{\texttt{F}}x_{t}^{\texttt{L}},y\rangle$
$\displaystyle\textstyle+\frac{1}{2}\mu_{t}^{\top}(R^{\texttt{F}}+(B^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}B^{\texttt{F}})\mu_{t}+\frac{1}{2}(x_{t}^{\texttt{L}})^{\top}(M^{\texttt{F}})^{\top}Q^{\texttt{F}}M^{\texttt{F}}x_{t}^{\texttt{L}}$
$\displaystyle+\langle(B^{\texttt{F}})^{\top}q_{t+1}^{\texttt{F}}+(B^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}A^{\texttt{F}}y,\mu_{t}\rangle-\frac{1}{2}\log\det\Sigma_{t}$
$\displaystyle\textstyle+\frac{1}{2}\mathop{\rm
tr}(\Sigma_{t}R^{\texttt{F}}+\Omega^{\texttt{F}}P_{t+1}+(B^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}B^{\texttt{F}}))+\nu_{t+1}^{\texttt{F}}.$

By setting the derivative of $V_{t}(y)$ with respect to $\mu_{t}$ and
$\Sigma_{t}$ to zero, we obtain (6). By substituting (6) into (26), we can
show that $V_{t}(y)=\frac{1}{2}y^{\top}P_{t}^{\texttt{F}}y+\langle
q_{t}^{\texttt{F}},y\rangle+\nu_{t}^{\texttt{F}}$, where $Q_{t}^{\texttt{F}}$
and $q_{t}^{\texttt{F}}$ satisfy (5).

Next, let
$K_{t}=-\Sigma_{t}(B^{\texttt{F}})^{\top}P_{t+1}^{\texttt{F}}A^{\texttt{F}}$
and $b_{t}=-\Sigma_{t}(B^{\texttt{F}})^{\top}q^{\texttt{F}}_{t+1}$. Then (6)
implies that
$u_{t}^{\texttt{F}}|x_{t}^{\texttt{F}}\sim\mathcal{N}(K_{t}x_{t}^{\texttt{F}}+b_{t},\Sigma_{t})$.
Since $x_{0}^{\texttt{F}}=\hat{x}^{\texttt{F}}_{0}$, by using the results in
[35, p. 91] we can show the following:

$\begin{bmatrix}x_{1}^{\texttt{F}}\\\
u_{1}^{\texttt{F}}\end{bmatrix}\sim\mathcal{N}\left(\begin{bmatrix}\xi_{0}\\\
K_{0}\xi_{0}+b_{0}\end{bmatrix},\begin{bmatrix}\Lambda_{0}&K_{0}\Lambda_{0}\\\
\Lambda_{0}K_{0}^{\top}&\Sigma_{0}+K_{0}^{\top}\Lambda_{0}K_{0}\end{bmatrix}\right).$

Therefore
$x_{t+1}^{\texttt{F}}=A^{\texttt{F}}x_{t}^{\texttt{F}}+B^{\texttt{F}}u_{t}^{\texttt{F}}+w_{t}^{\texttt{F}}\sim\mathcal{N}(\xi_{1},\Lambda_{1})$,
where $\xi_{1}$ and $\Sigma_{1}$ satisfy (7). By repeating similar steps for
$t\in[2,\tau]$ we can show that (7) holds for all $t\in[0,\tau-1]$, which
completes the proof.

## References

  * [1] V. A. Shia, Y. Gao, R. Vasudevan, K. D. Campbell, T. Lin, F. Borrelli, and R. Bajcsy, “Semiautonomous vehicular control using driver modeling,” _IEEE Trans. Intel. Transp. Syst._ , vol. 15, no. 6, pp. 2696–2709, 2014\.
  * [2] N. Mehr, R. Horowitz, and A. D. Dragan, “Inferring and assisting with constraints in shared autonomy,” in _Pro. IEEE Conf. Decision Control_. IEEE, 2016, pp. 6689–6696.
  * [3] N. Mehr, M. Wang, M. Bhatt, and M. Schwager, “Maximum-entropy multi-agent dynamic games: Forward and inverse solutions,” _IEEE Trans. Robot._ , 2023\.
  * [4] D. Sadigh, S. S. Sastry, S. A. Seshia, and A. Dragan, “Information gathering actions over human internal state,” in _Proc. Int. Conf. Intel. Robots Syst._ IEEE, 2016, pp. 66–73.
  * [5] K. Waugh, B. D. Ziebart, and J. A. Bagnell, “Inverse correlated equilibrium for matrix games,” _Adv. Neural Inform. Process. Syst._ , 2010.
  * [6] V. Kuleshov and O. Schrijvers, “Inverse game theory: Learning utilities in succinct games,” in _Int. Conf. Web Internet Econ._ Springer, 2015, pp. 413–427.
  * [7] D. Bertsimas, V. Gupta, and I. C. Paschalidis, “Data-driven estimation in equilibrium using inverse optimization,” _Math. Prog._ , vol. 153, no. 2, pp. 595–633, 2015.
  * [8] L. Peters, D. Fridovich-Keil, V. R. Royo, C. J. Tomlin, and C. Stachniss, “Inferring objectives in continuous dynamic games from noise-corrupted partial state observations,” in _Robotics: Sci. and Syst. 2021_ , 2021.
  * [9] T. L. Molloy, J. I. Charaja, S. Hohmann, and T. Perez, “Inverse optimal control and inverse noncooperative dynamic game theory,” 2022.
  * [10] Y. Yu, J. Salfity, D. Fridovich-Keil, and U. Topcu, “Inverse matrix games with unique quantal response equilibrium,” _IEEE Control Syst. Lett._ , vol. 7, pp. 643–648, 2022.
  * [11] J. Li, C.-Y. Chiu, L. Peters, S. Sojoudi, C. Tomlin, and D. Fridovich-Keil, “Cost inference for feedback dynamic games from noisy partial state observations and incomplete trajectories,” in _Proc. Int. Conf. Auton. Agents and Multiagent Syst._ , 2023, pp. 1062–1070.
  * [12] C. K. Ling, F. Fang, and J. Z. Kolter, “What game are we playing? end-to-end learning in normal and extensive form games,” in _Proc. Int. Joint Conf. Artif. Intell._ , 2018, pp. 396–402.
  * [13] S. Chen, Y. Yu, D. Fridovich-Keil, and U. Topcu, “Soft-bellman equilibrium in affine markov games: Forward solutions and inverse learning,” _arXiv preprint arXiv:2304.00163_ , 2023.
  * [14] T. Başar, “Affine incentive schemes for stochastic systems with dynamic information,” _SIAM J. Control Optim._ , vol. 22, no. 2, pp. 199–210, 1984\.
  * [15] N. Nisan and A. Ronen, “Algorithmic mechanism design,” _Games Econ. Behav_ , vol. 35, no. 1, pp. 359–379, 2015.
  * [16] M. Lopes, F. Melo, and L. Montesano, “Active learning for reward estimation in inverse reinforcement learning,” in _Proc. Eur. Conf. Mach. Learn. Knowl. Discovery Databases_. Springer Berlin Heidelberg, 2009, pp. 31–46.
  * [17] R. Akrour, M. Schoenauer, and M. Sebag, “April: Active preference learning-based reinforcement learning,” in _Proc. Eur. Conf. Mach. Learn. Knowl. Discovery Databases_. Springer, 2012, pp. 116–131.
  * [18] D. Sadigh, A. Dragan, S. Sastry, and S. Seshia, “Active preference-based learning of reward functions,” in _Robotics: Science and Systems XIII_ , July 2017.
  * [19] P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei, “Deep reinforcement learning from human preferences,” _Adv. Neural Inform. Process. Syst._ , vol. 30, 2017.
  * [20] C. Daniel, M. Viering, J. Metz, O. Kroemer, and J. Peters, “Active reward learning.” in _Robot.: Sci. Syst._ , vol. 98, 2014.
  * [21] E. Bıyık and D. Sadigh, “Batch active preference-based learning of reward functions,” in _Proc. Conf. Robot Learn._ PMLR, 2018, pp. 519–528.
  * [22] E. Bıyık, D. A. Lazar, D. Sadigh, and R. Pedarsani, “The green choice: Learning and influencing human decisions on shared roads,” in _Proc. IEEE Conf. Decision Control_. IEEE, 2019, pp. 347–354.
  * [23] M. Palan, G. Shevchuk, N. Charles Landolfi, and D. Sadigh, “Learning reward functions by integrating human demonstrations and preferences,” in _Robot.: Sci. Syst._ , 2019.
  * [24] S. M. Katz, A.-C. Le Bihan, and M. J. Kochenderfer, “Learning an urban air mobility encounter model from expert preferences,” in _Proc. IEEE/AIAA Digit. Avionics Syst. Conf._ IEEE, 2019, pp. 1–8.
  * [25] C. Basu, E. Bıyık, Z. He, M. Singhal, and D. Sadigh, “Active learning of reward dynamics from hierarchical queries,” in _Proc. IEEE/RSJ Int. Conf. Intell. Robots Syst._ IEEE, 2019, pp. 120–127.
  * [26] R. Cohn, E. Durfee, and S. Singh, “Comparing action-query strategies in semi-autonomous agents,” in _Proc. AAAI Conf. on Artif. Intell._ , vol. 25, no. 1, 2011, pp. 1102–1107.
  * [27] C. Daniel, O. Kroemer, M. Viering, J. Metz, and J. Peters, “Active reward learning with a novel acquisition function,” _Autonomous Robots_ , vol. 39, pp. 389–405, 2015.
  * [28] Y. Cui and S. Niekum, “Active reward learning from critiques,” in _Proc. IEEE Int. Conf. Robot. Automat._ IEEE, 2018, pp. 6907–6914.
  * [29] E. Bıyık, M. Palan, N. C. Landolfi, D. P. Losey, and D. Sadigh, “Asking easy questions: A user-friendly approach to active reward learning,” in _Conference on Robot Learning_. PMLR, 2020, pp. 1177–1190.
  * [30] V. Myers, E. Bıyık, N. Anari, and D. Sadigh, “Learning multimodal rewards from rankings,” in _Proc. Conf. Robot Learn._ PMLR, 2022, pp. 342–352.
  * [31] R. Horst and N. V. Thoai, “Dc programming: overview,” _J. Optim. Theory Appl._ , vol. 103, pp. 1–43, 1999.
  * [32] T. Lipp and S. Boyd, “Variations and extension of the convex–concave procedure,” _Optim. Eng._ , vol. 17, pp. 263–287, 2016.
  * [33] S. Dempe and A. Zemkoho, “Bilevel optimization,” in _Springer Optimization and Its Applications_. Springer, 2020, vol. 161.
  * [34] G. Lanckriet and B. K. Sriperumbudur, “On the convergence of the concave-convex procedure,” _Adv. Neural Inform. Process. Syst._ , vol. 22, 2009.
  * [35] C. M. Bishop and N. M. Nasrabadi, _Pattern recognition and machine learning_. Springer, 2006, vol. 4, no. 4.


23 2102

# Descriptional Complexity of Finite Automata – Selected Highlights

Arto Salomaa
Department of Mathematics
University of Turku
20014 Turku  Finland
<EMAIL_ADDRESS>Kai Salomaa
School of Computing
Queen’s University
Kingston  Ontario  Canada
<EMAIL_ADDRESS>Taylor J. Smith
Department of Computer Science
St. Francis Xavier University
Antigonish  Nova Scotia  Canada
<EMAIL_ADDRESS>
###### Abstract

The state complexity, respectively, nondeterministic state complexity of a
regular language $L$ is the number of states of the minimal deterministic,
respectively, of a minimal nondeterministic finite automaton for $L$. Some of
the most studied state complexity questions deal with size comparisons of
nondeterministic finite automata of differing degree of ambiguity. More
generally, if for a regular language we compare the size of description by a
finite automaton and by a more powerful language definition mechanism, such as
a context-free grammar, we encounter non-recursive trade-offs. Operational
state complexity studies the state complexity of the language resulting from a
regularity preserving operation as a function of the complexity of the
argument languages. Determining the state complexity of combined operations is
generally challenging and for general combinations of operations that include
intersection and marked concatenation it is uncomputable.

###### keywords:

finite automaton, state complexity, degree of ambiguity, regularity preserving
operation, undecidability

††volume: 185††issue: 1

Descriptional Complexity – Highlights

In honor of the 60th birthday of Iiro Honkala.

##  1 Introduction

Descriptional complexity studies the relative succinctness between different
representations of formal languages [1]. For a quantitative understanding of
regular languages the commonly used size measures count the number of states
or, in the case of nondeterministic finite automata, the number of
transitions. Early work on descriptional complexity of finite automata
includes [2, 3, 4, 5, 6].

One of the most important open problems in descriptional complexity was
originally raised by Sakoda and Sipser in 1978 [7]. The question asks whether
any two-way nondeterministic finite automaton $M$ has an equivalent
deterministic two-way automaton with a number of states bounded by a
polynomial on the number of states of $M$. Already Sakoda and Sipser
conjectured a negative answer to this question. Berman [8] and Sipser [9]
showed that if one proves an exponential gap in the succinctness of
nondeterministic and deterministic two-way automata and the strings involved
in the separation have polynomial length, this implies that deterministic
logarithmic space is a proper subset of nondeterministic logarithmic space.
Also Sipser [9] introduced a restricted version of two-way automata, called
sweeping automata, where the reading head may reverse only at the end-markers
and proved an exponential separation between nondeterministic and
deterministic sweeping automata. While the original question on the
succinctness comparison of nondeterministic and deterministic two-way automata
remains open, an exponential separation has been established, besides sweeping
automata, for several other restricted variants [10, 11, 12].

This brief survey discusses three specific descriptional complexity topics:
non-recursive trade-offs, the state complexity trade-off between
nondeterministic finite automata with differing degrees of ambiguity, and, the
state complexity of language operations. We generally focus on finite
automaton models, however, non-recursive trade-offs naturally deal with
succinctness comparisons with more powerful models. Descriptional complexity
is a large and active research area and more information can be found e.g. in
the surveys [13, 14, 15, 16, 17, 18, 12, 19].

##  2 Non-recursive trade-offs

In a seminal work Stearns [6] studied the relative succinctness of regular
languages represented by deterministic finite automata (DFA) and deterministic
pushdown automata (PDA). He showed that if a deterministic PDA recognizes a
regular language it can be a simulated by a DFA of triple-exponential size.
The work establishes also the decidability of regularity of the language of a
deterministic PDA. Generally the difference in succinctness of description
between different representations of a regular language can be arbitrary. This
phenomenon is referred to as a non-recursive trade-off.

More formally, a family of languages ${\cal L}$ is represented by a
descriptional system $S$ if ${\cal L}=\\{L({\cal R})\mid{\cal R}\in S\\}$.
Here $L({\cal R})$ is the language represented by descriptor ${\cal R}$. A
complexity measure is a total recursive function $c:S\rightarrow\mathbb{N}$.
For descriptional systems $S_{1}$ and $S_{2}$ equipped with a complexity
measure $c$, a function $f$ is said to be an upper bound for the size blow-up
for changing from system $S_{1}$ to $S_{2}$ if for every language $L$ that has
representations in both systems, for every representation ${\cal R}_{1}$ of
$L$ in $S_{1}$, the language $L$ has a representation ${\cal R}_{2}$ in
$S_{2}$ where $c({\cal R}_{2})\leq f(c({\cal R}_{1}))$. Note that, for
example, when considering the trade-off between finite automata and pushdown
automata we consider only the size of representations of regular languages.
The trade-off between two descriptional systems is said to be non-recursive if
it is not upper bounded by any recursive function.

A central part of descriptional complexity research deals with non-recursive
trade-offs. As a first non-recursive size blow-up, Meyer and Fischer [4]
showed that between finite automata and general context-free grammars for
regular languages the difference in economy of description can be arbitrary,
that is, the trade-off is not upper bounded by any recursive function.
Hartmanis [20] showed that the descriptional complexity trade-off between
deterministic and nondeterministic PDA is non-recursive, even if the
nondeterministic PDA is equipped with a proof in a formal system that it
defines a deterministic language. The proof is based on the fundamental idea
due to Hartmanis that invalid computations of a Turing machine can be encoded
as a context-free language [21].

A couple of years later, based on Gödel’s technique for non-recursive
shortening of proofs of formal systems by additional axioms, Hartmanis [1]
extended the method as a general technique for proving non-recursive
succinctness trade-offs. We state the result on non-recursive trade-offs using
the formulation by Kutrib [22] that is independent of a particular complexity
measure.

######  Theorem 2.1 ([1, 22])

Let $S_{1}$ and $S_{2}$ be descriptional systems for recursive languages. The
trade-off between $S_{1}$ and $S_{2}$ is non-recursive if the following
conditions hold.

There exists a descriptional system $S_{3}$ and a property $P$ that is not
semi-decidable for languages with a representation in $S_{3}$ such that, given
an arbitrary representation ${\cal R}\in S_{3}$, there exists an effective
procedure to construct a representation in $S_{1}$ for some language $L_{\cal
R}$ with the property that $L_{\cal R}$ has a representation in $S_{2}$ if and
only if $L({\cal R})$ does not have property $P$.

In fact, as noted in [22] most proofs appearing in the literature to establish
non-recursive trade-offs rely on a technique analogous to Theorem 2.1, or are
based on context-free language encodings of invalid Turing machine
computations from [21].

##  3 Ambiguity of NFAs and state complexity

The state complexity ${\rm sc}(L)$ (respectively, nondeterministic state
complexity ${\rm nsc}(L)$) of a regular language $L$ is the minimal number of
states of a DFA (respectively, of an NFA) for $L$. Already from [2, 4, 5] it
is known that, for some regular languages $L$, ${\rm sc}(L)=2^{{\rm nsc}(L)}$.

The degree of ambiguity of an NFA $A$ on a string $w$ is the number of
accepting computations of $A$ on $w$. The NFA $A$ is unambiguous (UFA) if any
string has at most one accepting computation. If the ambiguity of $A$ on any
string is bounded by a constant, $A$ is finitely ambiguouos (FNFA) and $A$ is
polynomially ambiguous (PNFA) if the degree of ambiguity of $A$ on input $w$
is bounded by a polynomial in the length of $w$.

Schmidt [23] developed methods to prove lower bounds for the size of UFAs and
showed that there exists an $n$-state UFA where the smallest equivalent DFA
requires $2^{\Omega(\sqrt{n})}$ states. The lower bound was improved by
different authors and Leiss [24] gives a construction of an $n$-state UFA with
multiple initial states where an equivalent DFA need $2^{n}$ states. Leung
[25] established the lower bound $2^{n}$ for determinization of an UFA with
one initial state, as well as, showed that there exists an $n$ state FNFA for
which any equivalent UFA needs $2^{n}-1$ states.

Ravikumar and Ibarra [26] first considered systematically succinctness
comparisons between FNFAs, PNFAs and general NFAs, and showed that any NFA
recognizing a bounded language can be converted to an FNFA with polynomial
size blow-up. Leung [27] gave an optimal separation between PNFAs and general
NFAs. Using communication complexity Hromkovič et al. [28] give a
significantly simplified proof for a super-polynomial separation of NFAs and
PNFAs, however, their proof does not give the exact optimal size blow-up
$2^{n}-1$.

######  Theorem 3.1 ([27])

For $n\in\mathbb{N}$ there exists an $n$-state NFA $A_{n}$ such that any PNFA
for the language $L(A_{n})$ needs $2^{n}-1$ states.

Ravikumar and Ibarra [26] also conjectured that polynomially ambiguous NFAs
can be significantly more succinct than finitely ambiguous NFAs. The question
was solved affirmatively by Hromkovič and Schnitger [29]. The below theorem
gives a simplified special case of the result in [29] that gives a
superpolynomial succinctness separation between NFAs with degree of ambiguity,
respectively, $O(m^{k-1})$ and $O(m^{k})$, $k\in\mathbb{N}$. However, the
lower bound for the separation of $n$-state PNFAs and FNFAs is not
$2^{\Theta(n)}$ and the precise trade-off in the economy of description
remains open.

######  Theorem 3.2 ([29])

For $n\in\mathbb{N}$ there exists a PNFA $A_{n}$ with number of states
polynomial in $n$ such that any FNFA recognizing the language $L(A_{n})$ has
at least $2^{\Omega(n^{\frac{1}{3}})}$ states.

Besides ambiguity the degree of nondeterminism can be measured, roughly
speaking, by counting the number of guesses in one computation [30] or by
counting the number of all computations. The tree width, a.k.a. leaf size or
path size of an NFA $A$ on input $w$ is the number of leaves of the
computation tree of $A$ on $w$ [31, 32, 18, 33]. It is easy to see that an NFA
with finite tree width can be determinized with polynomial size blow-up but
very little is known about succinctness comparisons of NFAs with different
non-constant tree width growth rates. For example, it remains open whether an
NFA with polynomial tree width may, in the worst case, require super-
polynomially more states than an equivalent unrestricted NFA. Similarly, the
succintness comparison between NFAs, respectively, of finite and polynomial
tree width remains open.

##  4 Operational state complexity

The effect of a regularity preserving operation $f$ on the size of the minimal
DFA (respectively, on the size of a minimal NFA) is the operational state
complexity of the operation. This is defined formally below.

###### Definition 4.1

If $f$ is an $m$-ary regularity preserving language operation, a
(deterministic) state complexity upper bound of $f$ is a function
$g:\mathbb{N}^{m}\rightarrow\mathbb{N}$ such that for any regular languages
$L_{1}$, …, $L_{m}$, the language $f(L_{1},\ldots,L_{m})$ has a DFA with at
most $g({\rm sc}(L_{1}),\ldots,{\rm sc}(L_{m}))$ states.

The nondeterministic state complexity of an operation $f$ is defined
similarly. A function $f_{\rm sc}:\mathbb{N}^{m}\rightarrow\mathbb{N}$ is the
precise worst-case state complexity of $f$ if $f_{\rm sc}$ is a state
complexity upper bound of $f$ and, furthermore, for any positive integers
$n_{1},\ldots,n_{m}$ there exist regular languages $L_{i}$ with ${\rm
sc}(L_{i})=n_{i}$, $i=1,\ldots,m$, and the minimal DFA for
$f(L_{1},\ldots,L_{m})$ has $f_{\rm sc}(n_{1},\ldots,n_{m})$ states.

The state complexity of language operations was first considered by Maslov [3]
but the paper remained unknown in the west. A systematic study of operational
state complexity of regular languages was initiated by S. Yu in the 1990’s
[19, 34]. The operational state complexity of extensions of finite automata
that have strong closure properties, such as input-driven pushdown automata,
a.k.a. visibly pushdown automata, has also been considered [35, 36].

In a series of papers Yu and co-authors have investigated the state complexity
of combined operations and have determined the precise worst-case state
complexity of all combinations of two basic language operations [37, 13].
Establishing matching upper and lower bounds for the state complexity of
combined language operations is often involved and Ésik et al. [38] have
introduced techniques to estimate the state complexity of combined operations.
For a general combination of operations that include marked concatenation and
intersection, Yu et al. [39] have shown that the question whether a given
integer function is a state complexity upper bound is undecidable in the
following sense.

The marked concatenation of languages $L_{1}$, $L_{2}$, …, $L_{n}$ is defined
as $L_{1}\sharp L_{2}\sharp\cdots\sharp L_{n}$ where $\sharp$ is a new symbol
not appearing in the languages $L_{i}$. A $(\cap,\sharp)$-composition over the
set $\\{L_{1},L_{2},\ldots,L_{n}\\}$, $n\geq 2$, of language variables is an
expression $\beta_{1}\sharp\beta_{2}\sharp\cdots\sharp\beta_{r}$, $r\geq 2$,
where each $\beta_{i}$ is of the form

$\beta_{i}=K_{1}\cap K_{2}\cap\cdots\cap K_{t_{i}},\;\;1\leq t_{i}\leq n,$

where $K_{j}$’s are distinct among the language variables $L_{i}$,
$i=1,\ldots,n$. A sequence of $(\cap,\sharp)$-compositions $C_{i}$,
$i=1,2,\ldots,$ is effectively constructible if there is an algorithm that on
input $i\in\mathbb{N}$ outputs $C_{i}$.

######  Theorem 4.2 ([39])

A sequence of $(\cap,\sharp)$-compositions $C_{i}$, can be effectively
constructed such that, given $i\in\mathbb{N}$ and a polynomial with positive
integer coefficients $P$ over the same number of variables as $C_{i}$, it is
undecidable whether or not $P$ is a state complexity upper bound for the
composition $C_{i}$ (as defined in Definition 4.1).

## References

  * [1] Hartmanis J.  On Gödel speed-up and succinctness of language representations.  _Theoretical Computer Science_ , 1983.  26(3):335–342.  10.1016/0304-3975(83)90016-6.
  * [2] Lupanov OB.  A comparison of two types of finite sourses (O sravnenii dvukh tipov konechnykh istochnikov).  _Problemy Kibernetiki_ , 1963.  9:321–326.
  * [3] Maslov AN.  Estimates of the number of states of finite automata.  _Soviet Math. Dokl._ , 1970.  11(5):1373–1375.
  * [4] Meyer AR, Fischer MJ.  Economy of description by automata, grammars, and formal systems.  In: Proceedings of SWAT 1971. IEEE, 1971 pp. 188–191.  10.1109/SWAT.1971.11.
  * [5] Moore FR.  On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata.  _IEEE Trans. Comput._ , 1971.  C-20(10):1211–1214.  10.1109/T-C.1971.223108.
  * [6] Stearns RE.  A regularity test for pushdown machines.  _Information and Control_ , 1967.  11(3):323–340.  10.1016/S0019-9958(67)90591-8.
  * [7] Sakoda WJ, Sipser M.  Nondeterminism and the size of two way finite automata.  In: Proceedings of STOC 1978. ACM, 1978 pp. 275–286.  10.1145/800133.804357.
  * [8] Berman P.  A note on sweeping automata.  In: Proceedings of ICALP 1980, volume 85 of _LNCS_. Springer, 1980 pp. 91–97.  10.1007/3-540-10003-2_62.
  * [9] Sipser M.  Lower bounds on the size of sweeping automata.  _Journal of Computer and System Sciences_ , 1980.  21(2):195–202.  10.1016/0022-0000(80)90034-3.
  * [10] Hromkovič J, Schnitger G.  Nondeterminism versus determinism for two-way finite automata: Generalizations of Sipser’s separation.  In: Proceedings of ICALP 2003, volume 2719 of _LNCS_. Springer, 2003 pp. 439–451.  10.1007/3-540-45061-0_36.
  * [11] Kapoutsis CA.  Two-way automata versus logarithmic space.  _Theory of Computing Systems_ , 2014.  55:421–447.  10.1007/s00224-013-9465-0.
  * [12] Pighizzini G.  Two-way finite automata: Old and recent results.  _Fundamenta Informaticae_ , 2013.  126(2–3):225–246.  10.3233/FI-2013-879.
  * [13] Gao Y, Moreira N, Reis R, Yu S.  A survey on operational state complexity.  _Journal of Automata, Languages and Combinatorics_ , 2017.  21(4):251–310.  10.25596/jalc-2016-251.
  * [14] Goldstine J, Kappes M, Kintala CMR, Leung H, Malcher A, Wotschke D.  Descriptional complexity of machines with limited resources.  _Journal of Universal Computer Science_ , 2002.  8(2):193–234.  10.3217/jucs-008-02-0193.
  * [15] Gruber H, Holzer M.  From finite automata to regular expressions and back — A summary on descriptional complexity.  _International Journal of Foundations of Computer Science_ , 2015\.  26(8):1009–1040.  10.1142/S0129054115400110.
  * [16] Gruber H, Holzer M, Kutrib M.  Descriptional complexity of regular languages.  In: Pin JÉ (ed.), Handbook of Automata Theory, volume 1, pp. 411–457. EMS Press, 2021.  10.4171/AUTOMATA-1/12.
  * [17] Holzer M, Kutrib M.  Descriptional and computational complexity of finite automata—A survey.  _Information and Computation_ , 2011.  209(3):456–470.  10.1016/j.ic.2010.11.013.
  * [18] Hromkovič J.  Descriptional complexity of finite automata: Concepts and open problems.  _Journal of Automata, Languages and Combinatorics_ , 2002.  7(4):519–531.  10.25596/jalc-2002-519.
  * [19] Yu S.  Regular languages.  In: Rozenberg G, Salomaa A (eds.), Handbook of Formal Languages, volume 1, pp. 41–110. Springer, 1997.  10.1007/978-3-642-59136-5_2.
  * [20] Hartmanis J.  On the succinctness of different representations of languages.  _SIAM Journal of Computing_ , 1980.  9(1):114–120.  10.1137/0209010.
  * [21] Hartmanis J.  Context-free languages and Turing machine computations.  In: Mathematical Aspects of Computer Science, volume 19 of _Proc. Sympos. Appl. Math._ American Mathematical Society, 1967 pp. 42–51.  10.1090/psapm/019/0235938.
  * [22] Kutrib M.  The phenomenon of non-recursive trade-offs.  _International Journal of Foundations of Computer Science_ , 2005\.  16(5):957–973.  10.1142/S0129054105003406.
  * [23] Schmidt EM.  Succinctness of descriptions of context-free, regular, and finite languages.  Ph.D. thesis, Cornell University, 1978.
  * [24] Leiss E.  Succinct representation of regular languages by boolean automata.  _Theoretcal Computer Science_ , 1981.  13(3):323–330.  10.1016/S0304-3975(81)80005-9.
  * [25] Leung H.  Descriptional complexity of NFA of different ambiguity.  _International Journal of Foundations of Computer Science_ , 2005\.  16(5):975–984.  10.1142/S0129054105003418.
  * [26] Ravikumar B, Ibarra OH.  Relating the type of ambiguity of finite automata to the succinctness of their representation.  _SIAM Journal of Computing_ , 1989.  18(6):1263–1282.  10.1137/0218083.
  * [27] Leung H.  Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata.  _SIAM Journal of Computing_ , 1998.  27(4):1073–1082.  10.1137/S0097539793252092.
  * [28] Hromkovič J, Seibert S, Karhumäki J, Klauck H, Schnitger G.  Communication complexity method for measuring nondeterminism in finite automata.  _Information and Computation_ , 2002.  172(2):202–217.  10.1006/inco.2001.3069.
  * [29] Hromkovič J, Schnitger G.  Ambiguity and communication.  _Theory of Computing Systems_ , 2011.  48:517–534.  10.1007/s00224-010-9277-4.
  * [30] Goldstine J, Kintala CMR, Wotschke D.  On measuring nondeterminism in regular languages.  _Information and Compututation_ , 1990.  86(2):179–194.  10.1016/0890-5401(90)90053-K.
  * [31] Björklund H, Martens W.  The tractability frontier for NFA minimization.  _Journal of Computer and System Sciences_ , 2012.  78(1):198–210.  10.1016/j.jcss.2011.03.001.
  * [32] Han YS, Salomaa A, Salomaa K.  Ambiguity, nondeterminism and state complexity of finite automata.  _Acta Cybernetica_ , 2017.  23(1):141–157.  10.14232/actacyb.23.1.2017.9.
  * [33] Palioudakis A, Salomaa K, Akl SG.  State complexity of finite tree width NFAs.  _Journal of Automata, Languages and Combinatorics_ , 2012.  17(2–4):245–264.  10.25596/jalc-2012-245.
  * [34] Yu S.  State complexity of regular languages.  _Journal of Automata, Languages and Combinatorics_ , 2001.  6(2):221–234.  10.25596/jalc-2001-221.
  * [35] Alur R, Madhusudan P.  Visibly pushdown languages.  In: Proceedings of STOC 2004. ACM, 2004 pp. 202–211.  10.1145/1007352.1007390.
  * [36] Okhotin A, Salomaa K.  Complexity of input-driven pushdown automata.  _ACM SIGACT News_ , 2014.  45(2):47–67.  10.1145/2636805.2636821.
  * [37] Cui B, Gao Y, Kari L, Yu S.  State complexity of combined operations with two basic operations.  _Theoretical Computer Science_ , 2012.  437:82–102.  10.1016/j.tcs.2012.02.030.
  * [38] Ésik Z, Gao Y, Liu G, Yu S.  Estimation of state complexity of combined operations.  _Theoretical Computer Science_ , 2009.  410(35):3272–3280.  10.1016/j.tcs.2009.03.026.
  * [39] Salomaa A, Salomaa K, Yu S.  Undecidability of state complexity.  _International Journal of Computer Mathematics_ , 2013.  90(6):1310–1320.  10.1080/00207160.2012.704994.