Projects

My group works at the interface of game theory, economics, control theory, optimization, (machine/statistical) learning, and artificial intelligence.
CPS 

Motivated by learning-enabled intelligent systems (e.g., intelligent infrastructure systems, platform based markets supporting e-commerce/healthcare/transportation/logistics, etc.), our research seeks algorithms and methodological innovations that have broad applicability. Learning-based markets and other forms of automated/algorithmic decision making are now commonplace in a variety of critical areas of our economy. And, algorithms are increasingly being incorporated into complex systems where they must learn in the presence of competition and execute sequences of decisions in the face of scarcity of resources, under uncertainties that influence the ability to robustly draw future inferences and satisfy downstream objectives, and in the presence of strategically generated (even adversarial) data. The research in my group seeks to develop algorithms for everything from inference to influence in non-stationary, uncertain, and competitive environments. Below are short descriptions of some the projects that align with this theme. A common thread across core research projects is the development of performance guarantees for coupled decision-making agents and/or learning algorithms and seeking such guarantees even in non-stationary environments.

Applications Areas: human-machine interaction & autonomy, online platforms/data markets, societal-scale systems (e.g., intelligent transportation systems).

Funding
This work is largely funded by the National Science Foundation ((CRII) CNS-1656873, (SCC) CNS-1736582, (CPS) CNS-1836819, (CPS) CNS-1931718, (RI) IIS/CSE-1907907, (CAREER) CNS-1844729, SCC Track 1 CNS-1952011), and the Office of Naval Research (ONR YIP)
Past funding: (CPS) CNS-1634136, (US-Ignite) CNS-1646912

Awards & Recognition
  • 2021 Junior Faculty Award, UW CoE
  • 2020 ONR Young Investigator Award
  • 2020 Dhanani Endowed Faculty Fellowship, UW
  • 2019 NAE, China-America Frontiers of Engineering Symposium, Invited Speaker
  • 2019 National Science Foundation CAREER Award
  • 2017 National Science Foundation CISE Research Initiation Initiative Award
  • 2009 National Science Foundation Graduate Research Fellowship
  • Selected Projects

    Certifiable Reinforcement Learning

    Many of the same kinds of uncertainties (particularly, those arising from human decision-makers) arise in a number of applications where research into the efficacy of reinforcement learning approaches to control and automation are being explored. For example, in (semi-)autonomous driving and robotic surgery applications humans are directly coupled with another autonomous agent and real-time decisions are being made often over short horizons where there is little time for cogitation and risk or reference points (e.g., past experiences) are the basis for decisions. We are developing algorithms for reinforcement learning with certificates of performance with assessment on benchmark problems. Applications include intelligent infrastructure (societal-scale CPS) and human-in-the-loop systems. [joint with Sam Burden (UW); Sam Coogan (GaTech)]
    CPS 
    Recent Papers :
    • Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games, Eric Mazumdar, Lillian J. Ratliff, Micheal I. Jordan, S. Shankar Sastry. AAMAS, arxiv:1907.0312, 2020.
    • Global Convergence of Policy Gradient for Sequential Zero-Sum Linear Quadratic Dynamic Games. Jingjing Bu, Lillian J. Ratliff, Mehran Mesbahi. arxiv:1911.04672, 2019.
    • Convergence Guarantees for Gradient-Based Learning in Continuous Games. Benjamin Chasnov, Lillian J. Ratliff, Eric Mazumdar, and Samuel Burden. Uncertainty in Artificial Intelligence (UAI), (pdf), 2019.

    Adaptive Mechanism Design and Multi-Sided Markets

    In situations of asymmetric information, we are designing incentive or information shaping schemes for changing user behavior via algorithmic mechanisms, with provable guarantees on performance, that leverage behavioral models capturing salient features of the human decision-making process. We take motivation from a number of applications including peer review (bidding and reviewer-paper matching), online labor markets (proposals and reverse selection), and incentive/information design in mobility applications including on-street parking, micro-vehicle sharing, concierge service companies (e.g., delivery on-demand), etc. [collaborators: K. Jamieson, UW; L. Jain, UW; Nihar Shah, CMU]
    Between Two Firms 
    Recent Papers:
    • Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences. Tanner Fiez, Shreyas Sekar, Liyuan Zheng, and Lillian J. Ratliff. Uncertainty in Artificial Intelligence (UAI), (pdf), 2018.
    • Adaptive Incentive Design. Lillian J. Ratliff and Tanner Fiez. IEEE Transactions on Automatic Control (under review), arxiv:1806.05749, 2018.
    • A Super* Algorithm to Determine Orderings of Items to Show Users. Tanner Fiez, Nihar Shah, and Lillian J. Ratliff. UAI, 2020 (full paper); Real-world Sequential Decision Making Workshop at ICML, 2019. (workshop version)
    • A Perspective on Incentive Design: Challenges and Opportunities. Lillian J. Ratliff, Roy Dong, Shreyas Sekar, and Tanner Fiez. Annual Reviews of Controls, Robotics, and Autonomous Systems, , 2019.
    • Competitive Settings Statistical Estimation with Strategic Data Sources. Tyler Westenbroek, Roy Dong, Lillian J. Ratliff. EC Workshop on Learning in the Presence of Strategic Behavior, (IEEE TAC 2019; CDC 2017), (pdf), 2019.
    • Incentive Design for Temporal Logic Objectives. Yagiz Savas, Vijay Gupta, Melkior Ornik, , Lillian J. Ratliff, Ufuk Topcu. IEEE CDC, 2019.
    • Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback Tanner Fiez, Shreyas Sekar, Lillian Ratliff. (arXiv:1803.04008), 2018.
    • Sequential Experimental Design for Transductive Linear Bandits. Tanner Fiez, Lalit Jain, Kevin Jamieson, Lillian J. Ratliff. NeuRIPs, (arxiv:1906.08399), 2019.

    Game Theory for Building Foundational ML Tools

    We often seek machine learning algorithms with guarantees on robustness to adversarially generated examples or strategically generated data. Increasingly the formulation of such problems takes the form of a game. For example, everything from adversarial learning to fair classification has been formulated as a minmax optimization problem or zero-sum game. Yet, many of the known results for such problems often assume a lot of problem structure (e.g., convexity of costs or full information) which is not present in machine learning problems, where non-convexity and limited information are quite common. In this line of research we seek to understand the optimization landscape for such problems and design algorithms that not only lead to game theoretically meaningful equilibria but learning algorithms with good performance and robustness guarantees.

    Multi-Modal

    Recent Papers:
    • Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with Finite Timescale Separation. Tanner Fiez and Lillian J. Ratliff. 2020 ( arxiv)
    • Evolutionary Game Theory Squared: Evolving Agents in Endogenously Evolving Games. Stratis Skoulakis, Tanner Fiez, Ryann Sim, Georgios Piliouras, Lillian J. Ratliff. AAAI Conference on Artificial Intelligence, 2021 ( arxiv)
    • Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study. Tanner Fiez, Benjamin Chasnov, Lillian J. Ratliff, International Conference on Machine Learning (ICML) 2020 (ICML link, arxiv 2019)
    • On Gradient-Based Learning in Continuous Games. Eric Mazumdar and Lillian J. Ratliff. SIAM Journal on Mathematics of Data Science (SIMODS), 2020 ( SIMODS pdf, arxiv 2018)

    Algorithmic Competition & Cooperation


    A number of machine learning problems are begin cast as games in order to learn more robust, better performing algorithms. On the other hand, the rise of multi-agent learning (e.g., AlphaGo) in non-stationary environments as well as competition between algorithms (e.g., in financial markets or online marketplaces) exposes the need for better analysis tools for the interaction between learning agents/algorithms. With these two observations in hand, our goal is to derive performance guarantees for classes of (competitive and cooperative) multi-agent learning algorithms in non-stationary environments. Such tools are useful for both analysis of the behavior of coupled learning agents as well as synthesizing mechanisms for shaping agent behavior. In addition, we seek to draw connections between dynamical systems theory (in particular, types of limiting behavior beyond equilibria) and learning dynamics.

    Multi-Modal

    Recent Papers:
    • On gradient-based learning in continuous games. Eric Mazumdar and Lillian J. Ratliff. SIAM Journal on Mathematics of Data Science (SIMODS), (pdf), 2019.
    • Implicit Learning Dynamics in Stackelberg Games: Equilibria Characterization, Convergence Analysis, and Empirical Study Tanner Fiez, Benjamin Chasnov, Lillian J. Ratliff. International Conferenece on Machine Learning (ICML) 2020 ( PMLR link, arxiv 2019)
    • Distributed Learning in Network Games: A Dual Averaging Approach. Shahriar Talebi, Siavash Alemzadeh, Lillian J. Ratliff, Mehran Mesbahi. IEEE CDC, (pdf) 2019.
    • Convergence Guarantees for Gradient-Based Learning in Continuous Games. Benjamin Chasnov, Lillian J. Ratliff, Eric Mazumdar, and Samuel Burden. Uncertainty in Artificial Intelligence (UAI), (pdf), 2019.
    • Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in 'Almost All' Zero-Sum Continuous Games. Eric Mazumdar and Lillian J. Ratliff. IEEE CDC, arxiv:2002.01007, 2019.
    • On the Characterization of Local Nash Equilibria in Continuous Games. Lillian J. Ratliff, Samuel A. Burden, S. Shankar Sastry. IEEE TAC, 2016
    • Genericity and structural stability of non-degenerate differential Nash equilibria. L. J. Ratliff, S. A. Burden, S. S. Sastry. ACC, 2014
    • Characterization and computation of local Nash equilibria in continuous games. L. J. Ratliff, S. A. Burden, S. S. Sastry. Allerton, 2013

    Applications

    Intelligent Transportation: Curbside & Real-Time Fleet Management
    A major source of motivation in some of the research we do are problems in urban mobility including curbside management and real-time fleet management for public transit. The emergence of novel digitally mediated markets for movement of goods and people as well as on-demand door-to-door services has lead to a number of interesting challenges requiring the careful design of market mechanisms that do not introduce new unintended outcomes such as unfair treatment of socioeconomic groups or increased congestion. Furthermore, a number of classical problems in transportation such as curbside management are revealing themselves to be very interesting problems to revisit with a modern perspective due to the availability of data and the new transit mechanisms such as ride-sharing, concierge services, and micro-vehicles (e.g., scooters, bikes, etc.).
    Between Two Firms 

    Curbside Management in Seattle, WA. Research in this direction has been conducted in collaboration with the Seattle Department of Transportation (on curbside management) where we have had impact on the way in which data is curated, analyzed and used to make policy decisions from pricing to resource allocation to assessing curb availability in development projects. We are developing methods of modeling and predicting occupancy from paid occupancy (block level paid transaction data indicating arrival and estimated departure of paying customers) and sparse groundtruth data from manual studies (walking around and counting cars) and timelapse cameras.

    This is challenging because the paid transactions do not provide the full picture for occupancy and ground truth data is sparse and expensive to collect. Typically one day per year per block is collected in Seattle. To address this, we are developing methods of actively (active learning via contextual pure exploration) selecting locations to target longer duration studies at locations that are the most informative in terms of improving the occupancy model quality.
    Between Two Firms 

    In addition, using the occupancy model, we are developing algorithms for designing mechanisms (information/incentives) to influence users behavior. In particular, the goal is to leverage information as a mechanism to encourage users to plan ahead so that they spend less time cruising looking for parking.
    Between Two Firms 

    Beyond parking, there are many use cases for curbspace in cities. We are looking at curbspace more generally by developing algorithmic mechanisms (e.g., auctions and matching markets) for what are known as flex zones, i.e., curbspace that allows for multiple uses such as commercial load zones, passenger load zones, transportation network companies/concierge services, etc.
    Between Two Firms 

    Real-time Public Transit Fleet Management in Chattanooga and Nashville, TN. Research on real-time fleet management is in collaboration with CARTA (Chattanooga Area Regional Transportation Authority), WeGo in Nashville TN, and Vanderbilt University (Abhishek Dubey, project lead). In this line of work we seek to design routing strategies for allocating micro-fleet vehicles that meet real-time demand for public transit by feeding into the fixed bus routes. More detail on this project can be found at Smarttransit.ai.
    Between Two Firms 
    Recent Papers:
    • Multi-Dimensional Continuous Type Population Potential Games. Daniel Calderone and Lillian J. Ratliff. IEEE CDC, 2019.
    • Modeling Curbside Parking as a Network of Finite Capacity Queues. Chase Dowling, Lillian J. Ratliff, Baosen Zhang. IEEE Transactions ITS, 2019.
    • Data-Driven Spatio-Temporal Analysis of Curbside Parking Demand. Tanner Fiez and Lillian J. Ratliff. IEEE Transactions ITS, 2019
    • Koopman Operator Approach for Instability Detection and Mitigation in Signalized Traffic. Esther Ling, Lillian J. Ratliff, and Samuel Coogan. In IEEE ITSC, 2018.
    • Uncertainty in Multi-Commodity Routing Networks: When does it help? Shreyas Sekar, Liyuan Zheng, Lillian J. Ratliff, and Baosen Zhang. IEEE TAC 2020 and ACC, 2018.
    • Optimizing Curbside Parking Resources Subject to Congestion Constraints. Chase Dowling, Tanner Fiez, Lillian J. Ratliff, and Baosen Zhang. IEEE CDC, 2017.
    • To observe or not to observe: Queuing game framework for urban parking. L. J. Ratliff, C. Dowling, E. Mazumdar, and B. Zhang. IEEE CDC, 2016.
    • Understanding the impact of parking on urban mobility via routing games on queue-flow networks. D. Calderone, E. Mazumdar, L. J. Ratliff, and S. S. Sastry. IEEE CDC, 2016.

    Human-Machine Interaction & Behavior Models of Humans
    Between Two Firms 
    Recent Papers:
    • Inverse Risk-Sensitive Reinforcement Learning. Lillian J. Ratliff and Eric Mazumdar. IEEE TAC, (arxiv:1703.09842), 2019.
    • Opponent Anticipation via Conjectural Variations. Benjamin Chasnov, Tanner Fiez, Lillian J. Ratliff. Smooth Games Optimization and Machine Learning Workshop: Bridging Game Theory and Deep Learning, NeuRIPS, (pdf); (longer working paper), 2019.
    • Learning Prospect Theory Value Function and Reference Point of a Sequential Decision Maker. Kamil Nar, Lillian J. Ratliff, S. Shankar Sastry. IEEE CDC, (pdf), 2017.
    • Leveraging Correlations in Utility Learning. Ioannis Konstantakopoulos, Lillian J. Ratliff, Ming Jin, Costas Spanos. ACC, 2017.
    • Inverse modeling of non-cooperative agents via mixture of utilities. I. C. Konstantakopoulos, L. J. Ratliff, M. Jin, C. J. Spanos, S. S. Sastry. IEEE CDC, 2016

    Online Platforms
    Between Two Firms 
    Recent Papers:
    • A Super* Algorithm to Determine Orderings of Items to Show Users. Tanner Fiez, Nihar Shah, Lillian J. Ratliff. Real-world Sequential Decision Making Workshop at ICML, 2019.
    • Sequential Experimental Design for Transductive Linear Bandits. Tanner Fiez, Lalit Jain, Kevin Jamieson, Lillian J. Ratliff. NeuRIPs, (arxiv:1906.08399), 2019.
    • Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences. Tanner Fiez, Shreyas Sekar, Liyuan Zheng, and Lillian J. Ratliff. Uncertainty in Artificial Intelligence (UAI), (pdf), 2018.
    • Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback Tanner Fiez, Shreyas Sekar, Lillian Ratliff. (arXiv:1803.04008), 2018.
    • Competitive Settings Statistical Estimation with Strategic Data Sources. Tyler Westenbroek, Roy Dong, Lillian J. Ratliff. EC Workshop on Learning in the Presence of Strategic Behavior, (IEEE TAC 2019; CDC 2017), (pdf), 2019.