Reward learning via human feedback is a crucial capability for beneficial AI. Current methods are built on decision-making theories that assume a matched dynamics model between the learning agent and the feedback provider. However, humans often form imperfect internal dynamics models, and their feedback reflects these misconceptions. While this relationship has long been hypothesised, its manifestation in sequential decision-making remains largely an assumption. Our work provides the first comprehensive empirical investigation of this relationship through a randomized controlled trial (N=211). We followed a two-stage design where we first initialized the participants' understanding of the dynamics in a grid-world navigation domain and then manipulated it using text-based instructions. Causal mediation analysis revealed that humans' internal models play a mediating role in feedback behaviour. We show that this relationship is invariant across visual contexts and is robust to three common feedback types: pairwise preferences, trajectory corrections, and off-switch interventions. These findings confirm a critical limitation of current reward learning methods and establish the missing psychological foundation for approaches that incorporate dynamics understanding.
论文检索
输入标题、作者或关键词，从 6,795 篇学术成果中精准定位
Coalition formation studies how to partition a set of agents into disjoint coalitions based on their preferences. In this paper, we consider the class of additively separable hedonic games and study the setting in which agents' valuations of each other evolve over time. Since rearranging coalitions can be costly, our goal is to find a stable partition close to the current one, where distance is measured by the number of agents that must change coalition. We study this problem for four stability notions based on single-agent deviations: Nash, individual, contractual Nash, and contractual individual stability. For all four, deciding whether a close stable partition exists is NP-complete, even under severe restrictions on the valuations and even when only a single valuation changes. On the positive side, we give polynomial-time algorithms for the two contractual notions under restricted symmetric valuations, and show that over long sequences of updates, these algorithms maintain stability with constant average reconfiguration cost.
In approval-based budget division, the task is to allocate a divisible resource to the candidates based on the voters' approval preferences over the candidates. For this setting, Brandl et al. (2021) have shown that no distribution rule can be strategyproof, efficient, and fair at the same time. In this paper, we aim to circumvent this impossibility theorem by focusing on approximate strategyproofness. To this end, we analyze the incentive ratio of distribution rules, which quantifies the maximum multiplicative utility gain of a voter by manipulating. While it turns out that several classical rules have a large incentive ratio, we prove that the Nash product rule (NASH) has an incentive ratio of 2, thereby demonstrating that we can bypass the impossibility of Brandl et al. by relaxing strategyproofness. Moreover, we show that an incentive ratio of 2 is optimal within three natural classes of rules and that the positive result for the Nash product rule even holds when voters may report arbitrary concave utility functions. Finally, we complement our results with an experimental analysis.
A common criticism of liquid democracy within the relevant academic literature is that delegation cycles can occur, seemingly resulting in unused voting power. Yet, practitioners argue that delegation cycles are not only unproblematic but are even formed intentionally by participants. To bring theory closer to reality, we introduce a model that captures this strategic behavior under uncertainty. We study the existence, structure and quality of Nash equilibria, revealing that delegation cycles naturally emerge. To complement these findings, we perform computational experiments using best-response dynamics.
For minimally rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations). Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory, but exhaustive search quickly becomes infeasible due to the super-exponential growth of the number of candidate graphs and the high cost of realization-count evaluation. We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves. We optimize realization-count invariants using the Deep Cross-Entropy Method with a policy parameterized by a Graph Isomorphism Network encoder and a permutation-equivariant extension-level action head. Empirically, our method matches the known optima for planar realization counts and improves the best known bounds for spherical realization counts, yielding new record graphs.
Coverage-based prime implicant explanations are formal explanations offering a number of valuable assets, especially in terms of faithfulness and generality. Unfortunately, deriving a coverage-based prime implicant explanation for an instance is computationally hard in the general case (the problem of identifying such an explanation being at the second level of the polynomial hierarchy). In this paper, we focus on the computation of a coverage-based prime implicant explanation for an instance given a tree-based model. We show that the specific nature of the domain theory linking the Boolean conditions in such models makes the problem computationally easier. We present a greedy algorithm to derive coverage-based prime implicant explanations when dealing with a tree-based model. We also present an empirical evaluation showing that this algorithm is efficient enough to be used in many practical cases.
Artificial intelligence models typically perform well on large-scale datasets, yet their effectiveness tends to degrade in real-world scenarios with scarce data, such as medical diagnostics. In contrast, humans can learn and reason effectively from few examples. Even when novel objects differ significantly from prior observations, humans can quickly infer category distributions accurately. Inspired by this, we explore how to leverage human-inspired cognitive mechanisms to improve the distribution calibration in few-shot learning models. Based on the ``fast-slow thinking'' dual-process theory, we propose a novel cognition-inspired few-shot learning framework. It mimics the human cognition when handling novel information: it first rapidly screens relevant knowledge through ``fast thinking'' and then infers inter-class relationships and calibrates distributions via ``slow thinking''. Specifically, the fast-thinking stage employs a gating mechanism to quickly match input samples with known base-class prototypes, activating relevant candidate knowledge. In the slow-thinking stage, the model aggregates inter-class edge embeddings into a summary relation graph and then applies divergent Gaussian sampling to generate multiple relation graphs representing different association strengths, thereby achieving distribution calibration for few-shot classes. Experiments on public few-shot benchmarks and medical image datasets show competitive performance. Visualization analyses further reveal that our framework exhibits meaningful interpretability.
Knowledge Tracing (KT) is fundamental to intelligent education systems, yet relies on educational logs that are selectively observed. The non-random nature of exercise recommendations and student choices inevitably induces severe selection bias. Most existing KT methods neglect this issue, training on observed logs using standard empirical risk, which yields biased mastery estimates and accumulates errors in subsequent recommendations. To address this, we introduce a doubly robust (DR) formulation for KT that integrates a propensity model with an error imputation model, theoretically guaranteeing unbiasedness if either model is accurate. Beyond unbiasedness, in the sequential setting of KT, we identify that the estimator's performance is compromised by variance-dependent stochastic deviations that accumulate over time, thereby causing training instability and limiting performance. To mitigate this, we derive a generalization bound that explicitly characterizes the impact of estimator variance and identifies temporal smoothness as a key factor in controlling it. Building on these theoretical insights, we propose the Temporal Smoothness Doubly Robust (TSDR) framework. TSDR jointly optimizes the KT predictor and the imputation model with a smoothness regularizer, effectively reducing variance while preserving the unbiasedness guarantee of DR. Experiments on multiple real-world benchmarks demonstrate that TSDR consistently enhances various state-of-the-art KT backbones, underscoring the vital role of principled bias correction in KT.
Many multiagent systems depend on collective decisions made by self-interested agents, which raises deep questions about coalition formation and stability. We study social choice with endogenous, outcome-contingent transfers, where agents voluntarily form contracts that redistribute utility depending on the collective decision, allowing for fully strategic coalition formation. We show that under consensus rules, individually rational strong Nash equilibria (IR–SNE) always exist, implementing welfare-maximizing outcomes with feasible transfers, and provide a simple, efficient algorithm to construct them. For more general anonymous, monotonic, and resolute rules, we identify necessary conditions for viable deviations, significantly limiting the possibility of destabilizing coalitions. By bridging cooperative and noncooperative perspectives, our approach shows that transferable utility can achieve core-like stability, restoring efficiency and budget balance even where classical impossibility results generally apply. Overall, this framework offers a practical and robust way to coordinate large-scale strategic multiagent systems.
Problems defined on binary decision spaces have been intensively studied in the theory of multi-objective evolutionary algorithms (MOEAs). In contrast, no mathematical runtime analyses exist so far for MOEAs dealing with decision variables that take a finite number r > 2 of values, despite the prevalence of such problems in practice. In this work, we begin to fill this research gap. We analyze how the classic SEMO algorithm with unit-strength local mutation computes the Pareto front of an r-valued counterpart of the classic ONEMINMAX benchmark. For the expected number of function evaluations until the Pareto front is covered by the population of this MOEA, we prove an upper bound of O(n²r² log n) and a near-tight lower bound of Ω(n²r(r + log n)). We can close the small remaining gap between these two bounds by considering a variant of the algorithm that accepts only strictly better solutions; for this variant, we show an upper bound of O(n²r(r + log n)), matching our lower bound, which also holds for this variant. Our results suggest that classic MOEAs encounter no significant additional difficulties when dealing with multi-valued decision variables. However, significantly more advanced tools may be required to obtain tight bounds for algorithms with more complex population dynamics.
We study a robust scheduling problem on identical machines in which machines may fail after the initial assignment. The goal is to compute an initial schedule together with a recovery strategy that minimizes the post-failure makespan, under the constraint that jobs on available machines cannot be moved. We consider two failure models: a strong adversary, which selects the failed machines, and a weak adversary, which selects only the number of failures. For up to k failures, we give algorithms with robustness ratios 1.618 for the strong adversary and 1.5 for the weak adversary. For the single-failure case, k = 1, we obtain best possible ratios 1.387 and 1.281, respectively, matching our lower bounds.
We investigate the complexity of stable (or perturbation-resilient) instances of k-Means and k-Median clustering problems in metrics with small doubling dimension. While these problems have been extensively studied under multiplicative perturbation resilience in low-dimensional Euclidean spaces, we adopt a more general notion of stability, termed "almost stable", known from the literature as (alpha,epsilon)-perturbation resilience. Additionally, we extend our results to k-Means/k-Median with penalties, where each data point is either assigned to a cluster centre or incurs a penalty. We show that certain special cases of almost stable k-Means/k-Median (with penalties) are solvable in polynomial time. To complement this, we also examine the hardness of almost stable instances and (1 + 1/poly(n))-stable instances of k-Means/k-Median (with penalties), proving super-polynomial lower bounds on the runtime of any exact algorithm under the widely believed Exponential Time Hypothesis (ETH).
Argumentation dynamics provides techniques for revising argumentation theories in real-world domains (e.g., an autonomous medical diagnostic agent). Within this context, enforcement in abstract argumentation has become a prominent topic. Enforcement aims to modify an argumentation framework to satisfy given acceptability conditions while minimizing change from the original framework. Motivated by the need to address both syntactic and semantic notions of change, we propose formula-based enforcement, a generic framework that strictly generalizes existing approaches, by additionally covering cases they cannot handle, including semantic change. We analyze its complexity under central argumentation semantics, obtaining results from NP-completeness to completeness for the third level of the polynomial hierarchy. For second-level complete variants, we present an exact procedure based on MaxSAT solving and counterexample-guided abstraction refinement (CEGAR), and evaluate it empirically.
The diffusion auction is an emerging auction model which leverages social networks to recruit more buyers, thereby improving auction revenue and allocation efficiency. Previous studies on diffusion auctions have primarily focused on the single-parameter domain, where each buyer's valuation function is represented by a single private value. However, due to the complex interdependencies between allocations and network structures, few studies have examined the combinatorial auction domain, in which buyers' valuation functions exhibit multidimensionality. In this paper, we fully characterize implementable diffusion mechanisms within the combinatorial auction domain for the first time. Based on the characterization, we identify a class of allocation policies for each of which the optimal payment, namely the one maximizing the seller's revenue, can be derived in closed form. Furthermore, we apply the established theory to design a practical diffusion combinatorial auction, named the Exhausted-Reference Pricing Mechanism, which is incentive-compatible, individually rational, and weakly budget balanced.
Multi-label data often contain high-dimensional features, outlier instances, and noisy labels, all of which can lead to the curse of dimensionality and decreased performance in downstream tasks. Although numerous data reduction methods have been developed, existing approaches face two major limitations: 1) existing methods typically select features, instances, or labels independently, without considering how noise or redundancy in one dimension may negatively influence the selection of others; 2) there are very few feature and instance co-selection methods that commonly assume label annotations are free of noise, which is seldom true in practice. To address these issues, we propose Evidential Multi-Label Multi-Dimensional Selection (EMMS), which jointly performs feature, instance, and label selection on multi-label data. EMMS introduces a dual projection mechanism with sparsity constraints that transforms high-dimensional data first into a latent space and then into the label space. Simultaneously, projection residuals are explicitly modeled to facilitate the identification of representative instances, enabling unified selection across features, instances, and labels. Moreover, EMMS employs evidence theory to fuse instance-level and label-level evidence, thereby enhancing the reliability of the learned labels and reducing the influence of noisy labels, which in turn promotes multi-dimensional selection. Extensive experiments demonstrate that EMMS consistently outperforms state-of-the-art methods.
Online goal recognition in continuous domains poses two central challenges: efficiently encoding large trajectories and effectively comparing them. Recent work addresses these challenges by using custom state-space representations and metrics to compare observations against hypotheses. However, these approaches often overlook well-established encoding techniques used in other domains that offer substantial advantages. This paper introduces a novel method for online goal recognition that leverages path signatures, a compact, expressive representation of rough path theory that captures key semantic features of trajectories in an efficient way, enabling more meaningful comparisons between them. Experiments show that our method consistently outperforms the state of the art in predictive accuracy and online planning efficiency, while remaining competitive offline.
The Spherical Sliced Wasserstein (SSW) distance has emerged as a fundamental tool for comparing probability measures on the hypersphere, with broad applications spanning geology, medical imaging, computer vision, and representation learning. However, its reliance on uniformly sampling a large number of projection directions from the unit hypersphere can lead to suboptimal performance, as many directions are weakly informative and fail to capture salient differences between distributions. We address this limitation through Fusion Stereographic Spherical Sliced Wasserstein (FS3W), a data-adaptive divergence that incorporates distribution-dependent information into projection selection. FS3W uses a neural slicing fusion mechanism to refine prior directions, steering them toward projections aligned with discriminative geometric structures in the data. This adaptive approach produces more expressive and accurate characterizations of distributional discrepancies on the hypersphere. We evaluate FS3W across five diverse tasks, including gradient flows, Earth density estimation, and self-supervised representation learning. Empirical results consistently demonstrate that FS3W outperforms existing spherical optimal transport–based methods.
Many practical decision-making problems involve tasks whose success depends on the entire system history, rather than on achieving a state with desired properties. Markovian Reinforcement Learning (RL) can be inadequate for such tasks, while modeling them as non-Markovian reward decision processes (NMRDPs) enables agents to handle temporal dependencies. Existing approaches offer limited formal guarantees on both (near-)optimality and sample efficiency. We address both issues with QR-max, a novel model-based algorithm for NMRDPs with discrete actions that factorizes Markovian transition learning from non-Markovian reward handling via reward machines. To our knowledge, this is the first model-based RL algorithm for discrete-action NMRDPs that leverages this factorization to obtain PAC convergence to ε-optimal policies with polynomial sample complexity. We then extend QR-max to continuous state spaces with Bucket-QR-max, a SimHash-based discretizer that preserves the same factorized structure and achieves fast and stable learning without manual gridding or function approximation. We experimentally compare our method with state-of-the-art model-based RL approaches on environments of increasing complexity, showing substantially improved sample efficiency and greater robustness in finding optimal policies.
We study repeated allocation of shared resources among agents with time-varying demands and capped linear utilities. In this setting, independently maximizing the minimum utility in each round satisfies sharing incentives (agents weakly prefer participating in the mechanism to not participating), strategyproofness (agents have no incentive to misreport their demands), and Pareto efficiency. However, this max-min mechanism can lead to large disparities in the total resources received by agents, even when they have the same average demand. We introduce credit fairness, a property that, together with Pareto efficiency, strengthens sharing incentives by ensuring that agents who lend resources in early rounds are able to recoup them in later rounds. Credit fairness can be achieved in conjunction with either Pareto efficiency or strategyproofness individually, but we show that, under anonymity, it cannot be achieved together with both. We propose a mechanism that is credit fair and Pareto efficient, and evaluate it in a computational resource-sharing setting.
Stochastic gradient methods are central to large-scale learning, yet their generalization theory typically relies on independent sampling assumptions. In many practical applications, data are generated by Markov chains and learning is performed in a decentralized manner, which introduces significant analytical challenges. In this work, we investigate the stability and generalization of decentralized stochastic gradient descent (SGD) and stochastic gradient descent ascent (SGDA) under Markov chain sampling. Leveraging a stability-based framework, we characterize how Markovian dependence and decentralized communication jointly influence generalization behavior. Our analysis captures the effects of network topology, Markov chain mixing properties, and primal–dual dynamics. We establish non-asymptotic generalization bounds for both algorithms, extending existing results on Markov stochastic gradient methods to decentralized and minimax settings.