Abstraction-Based Decision Making for Statistical Properties (Invited Talk)

Yonathan Efroni, Shie Mannor, Matteo Pirotta, Kueffner, Konstantin, Mallik, Kaushik

Abstract

Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service.

Introduction

Sequential decision-making involves an agent interacting with an uncertain environment over a fixed time horizon. At each step, the environment provides an input (e.g., a customer's bid), and the agent selects an output (e.g., accepting or rejecting the bid) to maximize a reward while adhering to cost constraints.

The primary obstacle in this field is the "state-space explosion." To determine an optimal strategy, standard algorithms often need to account for every possible sequence of past events. Since the number of sequences grows exponentially with time, finding an optimal strategy is generally PSPACE-hard. This computational barrier makes it impossible to solve for long time horizons using traditional methods. This research identifies a subset of problems solvable in polynomial time (PTIME) by focusing on "statistical properties."

Methodology: Statistical Abstraction

The core innovation of this work is the concept of statistical properties—objectives where the outcome depends on aggregated statistics of history rather than the specific order of events. For example, "how many times a client won" is statistical, whereas "did the client win on the third step" is order-dependent.

Counter Automata

The authors formalize these properties using automata equipped with a finite set of counters. If a goal, such as minimizing maximum wait time, can be tracked by a small set of counters, it qualifies as a statistical property.

Statistical-DP

By employing statistical abstraction, the algorithm clusters histories that result in identical counter values into "equivalence classes." Instead of treating every unique history as a separate state, the algorithm operates on these abstracted classes. The authors adapted the standard Dynamic Programming (DP) algorithm to work on these abstractions. Because the number of counter-value combinations grows only polynomially with the time horizon, the resulting "Statistical-DP" algorithm is exponentially more efficient than standard DP.

Application Scenarios

The algorithm was evaluated across three synthetic application scenarios modeled after real-world economic problems:

  1. Balanced Servers: Two clients bid for service. The agent maximizes profit while ensuring neither client is "starved" by maintaining a balanced frequency of service.
  2. Maximally Responsive Servers: The agent minimizes the maximum time any client waits for service, subject to a budget on "opportunity cost" (profit lost by not selecting the highest bidder).
  3. Clientele-aware Servers: A dynamic model where a client’s future bidding behavior is influenced by whether their previous bids were accepted or rejected.

Results and Discussion

The researchers compared Statistical-DP against a standard DP approach with significant findings:

  • Scalability: Standard DP failed due to memory exhaustion (exceeding a 200 GB limit) for time horizons as short as 10 steps. Conversely, the abstraction-based algorithm successfully handled horizons of up to 60,000 steps in the balanced server scenario.
  • Efficiency: In the "Maximally Responsive" scenario, the algorithm reached horizons of 400 steps in under a second, whereas the standard approach failed to initialize.
  • Policy Quality: Simulations demonstrated that the synthesized policies were not only computationally efficient but also highly effective. They maintained strict fairness constraints while achieving profits nearly identical to "greedy" strategies that ignore fairness entirely.

Conclusion

This work identifies a clear boundary of tractability in sequential decision-making. While order-dependent properties like "discounted sums" remain hard, statistical properties like "maximum wait time" can be solved efficiently. Using counter automata provides a systematic framework for translating high-level requirements into optimizable formats.

Future work will focus on extending these methods to infinite time horizons, where counters could theoretically grow indefinitely. Additionally, the authors aim to explore multi-objective trade-offs to find Pareto-optimal solutions balancing competing goals like profit, speed, and fairness.

Summary updated

Abstract

Sequential decision-making in probabilistic environments is a fundamental problem with many applications in AI and economics. In this paper, we present an algorithm for synthesizing sequential decision-making agents that optimize statistical properties such as maximum and average response times. In the general setting of sequential decision-making, the environment is modeled as a random process that generates inputs. The agent responds to each input, aiming to maximize rewards and minimize costs within a specified time horizon. The corresponding synthesis problem is known to be PSPACE-hard. We consider the special case where the input distribution, reward, and cost depend on input-output statistics specified by counter automata. For such problems, this paper presents the first PTIME synthesis algorithms. We introduce the notion of statistical abstraction, which clusters statistically indistinguishable input-output sequences into equivalence classes. This abstraction allows for a dynamic programming algorithm whose complexity grows polynomially with the considered horizon, making the statistical case exponentially more efficient than the general case. We evaluate our algorithm on three different application scenarios of a client-server protocol, where multiple clients compete via bidding to gain access to the service offered by the server. The synthesized policies optimize profit while guaranteeing that none of the server’s clients is disproportionately starved of the service.
BibTeX
@inproceedings{efroni2024abstraction,
  author = {Yonathan Efroni and Shie Mannor and Matteo Pirotta and Kueffner, Konstantin and Mallik, Kaushik},
  title = {{Abstraction-Based Decision Making for Statistical Properties (Invited Talk)}},
  booktitle = {DROPS},
  year = {2024},
  doi = {10.4230/lipics.fscd.2024.2},
}
Figure