Creating a domain model, even for classical, domain-independent planning, is a notoriously hard knowledge-engineering task. A natural approach to solve this problem is to learn a domain model from observations. However, model learning approaches frequently do not provide safety guarantees: the learned model may assume actions are applicable when they are not, and may incorrectly capture actions' effects. This may result in generating plans that will fail when executed. In some domains such failures are not acceptable, due to the cost of failure or inability to replan online after failure. In such settings, all learning must be done offline, based on some observations collected, e.g., by some other agents or a human. Through this learning, the task is to generate a plan that is guaranteed to be successful. This is called the model-free planning problem. Prior work proposed an algorithm for solving the model-free planning problem in classical planning. However, they were limited to learning grounded domains, and thus they could not scale. We generalize this prior work and propose the first safe model-free planning algorithm for lifted domains. We prove the correctness of our approach, and provide a statistical analysis showing that the number of trajectories needed to solve future problems with high probability is linear in the potential size of the domain model. We also present experiments on twelve IPC domains showing that our approach is able to learn the real action model in all cases with at most two trajectories.
This content will become publicly available on August 24, 2024
Welfare Effects of Ex-Ante Bias and Tie-Breaking Rules on Observational Learning with Fake Agents
Networks that provide agents with access to a common database of the agents' actions enable an agent to easily learn by observing the actions of others, but are also susceptible to manipulation by “fake” agents. Prior work has studied a model for the impact of such fake agents on ordinary (rational) agents in a sequential Bayesian observational learning framework. That model assumes that ordinary agents do not have an ex-ante bias in their actions and that they follow their private information in case of an ex-post tie between actions. This paper builds on that work to study the effect of fake agents on the welfare obtained by ordinary agents under different ex-ante biases and different tie-breaking rules. We show that varying either of these can lead to cases where, unlike in the prior work, the addition of fake agents leads to a gain in welfare. This implies that in such cases, if fake agents are absent or are not adequately present, an altruistic platform could artificially introduce fake actions to effect improved learning.
more »
« less
- Award ID(s):
- 1908807
- NSF-PAR ID:
- 10490467
- Publisher / Repository:
- IEEE
- Date Published:
- ISSN:
- 2690-3342
- Page Range / eLocation ID:
- 334 to 341
- Format(s):
- Medium: X
- Location:
- Singapore, Singapore
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
-
Effective management of social-ecological systems (SESs) requires an understanding of human behavior. In many SESs, there are hundreds of agents or more interacting with governance and regulatory institutions, driving management outcomes through collective behavior. Agents in these systems often display consistent behavioral characteristics over time that can help reduce the dimensionality of SES data by enabling the assignment of types. Typologies of resource-user behavior both enrich our knowledge of user cultures and provide critical information for management. Here, we develop a data-driven framework to identify resource-user typologies in SESs with high-dimensional data. To demonstrate policy applications, we apply the framework to a tightly coupled SES, commercial fishing. We leverage large fisheries-dependent datasets that include mandatory vessel logbooks, observer datasets, and high-resolution geospatial vessel tracking technologies. We first quantify vessel and behavioral characteristics using data that encode fishers’ spatial decisions and behaviors. We then use clustering to classify these characteristics into discrete fishing behavioral types (FBTs), determining that 3 types emerge in our case study. Finally, we investigate how a series of disturbances applied selection pressure on these FBTs, causing the disproportionate loss of one group. Our framework not only provides an efficient and unbiased method for identifying FBTs in near real time, but it can also improve management outcomes by enabling ex ante investigation of the consequences of disturbances such as policy actions.more » « less
-
In many predictive decision-making scenarios, such as credit scoring and academic testing, a decision-maker must construct a model that accounts for agents' incentives to ``game'' their features in order to receive better decisions. Whereas the strategic classification literature generally assumes that agents' outcomes are not causally dependent on their features (and thus strategic behavior is a form of lying), we join concurrent work in modeling agents' outcomes as a function of their changeable attributes. Our formulation is the first to incorporate a crucial phenomenon: when agents act to change observable features, they may as a side effect perturb unobserved features that causally affect their true outcomes. We consider three distinct desiderata for a decision-maker's model: accurately predicting agents' post-gaming outcomes (accuracy), incentivizing agents to improve these outcomes (improvement), and, in the linear setting, estimating the visible coefficients of the true causal model (causal precision). As our main contribution, we provide the first algorithms for learning accuracy-optimizing, improvement-optimizing, and causal-precision-optimizing linear regression models directly from data, without prior knowledge of agents' possible actions. These algorithms circumvent the hardness result of Miller et al. (2019) by allowing the decision maker to observe agents' responses to a sequence of decision rules, in effect inducing agents to perform causal interventions for free.more » « less
-
A new generation of poverty programs around the globe provides cash payments to poor and vulnerable households. Studies show that these social cash transfer programs create income and welfare benefits for poor households and the local economies where they live. However, this may come at the cost of damaging local environments if cash payments stimulate food production that conflicts with natural resource conservation. Evaluations of the economic impacts of poverty programs do not account for the welfare consequences of environmental impacts, which are potentially large for poor communities closely tied to natural resources. We use an ex-ante policy simulation tool, a bioeconomic local computable general equilibrium model parameterized with microsurvey data, to analyze the expected welfare consequences of environmental degradation caused by a cash transfer program. For a Philippine fishing community that is a net importer of fish, we show that a government cash transfer program initially increases real incomes for all households. However, increased demand for fish leads to a decline in the local fish stock that reduces program benefits. Household groups experience declines in real income benefits of 2–63%, with fishing households suffering the largest declines. Impacts on local fish stocks depend on the extent to which markets link fishing communities to outside regions through trade. Greater market integration can mitigate the fish stock decline, but this reduces the local income benefits of cash transfers.more » « less
-
We present an agent-based model of manipulating prices in financial markets through spoofing: submitting spurious orders to mislead traders who learn from the order book. Our model captures a complex market environment for a single security, whose common value is given by a dynamic fundamental time series. Agents trade through a limit-order book, based on their private values and noisy observations of the fundamental. We consider background agents following two types of trading strategies: the non-spoofable zero intelligence (ZI) that ignores the order book and the manipulable heuristic belief learning (HBL) that exploits the order book to predict price outcomes. We conduct empirical game-theoretic analysis upon simulated agent payoffs across parametrically different environments and measure the effect of spoofing on market performance in approximate strategic equilibria. We demonstrate that HBL traders can benefit price discovery and social welfare, but their existence in equilibrium renders a market vulnerable to manipulation: simple spoofing strategies can effectively mislead traders, distort prices and reduce total surplus. Based on this model, we propose to mitigate spoofing from two aspects: (1) mechanism design to disincentivize manipulation; and (2) trading strategy variations to improve the robustness of learning from market information. We evaluate the proposed approaches, taking into account potential strategic responses of agents, and characterize the conditions under which these approaches may deter manipulation and benefit market welfare. Our model provides a way to quantify the effect of spoofing on trading behavior and market efficiency, and thus it can help to evaluate the effectiveness of various market designs and trading strategies in mitigating an important form of market manipulation.more » « less
