Understanding underlying agent attributes such as goals, preferences, beliefs, and ability level is key to explaining decision-making and predicting behaviour in complex environments. While goal recognition (GR) has produced effective methods for inferring goals, recent work has begun to explore reinforcement learning (RL)-based approaches to attribute recognition (AR), which generalises GR by inferring a wider range of agent attributes beyond goals. Existing frameworks treat attributes as discrete variables and typically require separate models for each attribute. In reality, many agent attributes vary continuously rather than as discrete values, making continuous representations crucial for capturing subtle variations in behaviour. We introduce a multivariate RL-based AR framework that jointly infers multiple continuous-valued attributes from observed behaviour using a single attribute-conditioned policy and continuous probabilistic inference. Our experiments demonstrate that the proposed framework achieves stable and fine-grained inference, offering improved flexibility and generality compared to existing approaches.
论文检索
输入标题、作者或关键词，从 4,693 篇学术成果中精准定位
Our work evolves around Fictitious Play, one of the first iterative methods that is known to converge to a Nash equilibrium in zero-sum games. In recent years, there has been a revived interest, due to applications in various machine learning problems, which has motivated a line of work on its convergence properties and on proposing new variants of the initial algorithm. Our paper is along this direction and introduces one new variant, which we refer to as Almost Greedy Fictitious Play. The proposed algorithm greedily attempts to find the optimal stepsize at each iteration but its search space is constrained and includes almost all the line between the cumulative mixed strategy and the current best response. Our main result is that the method achieves an instance dependent convergence rate of O(1/T) with respect to the duality gap. This matches the rate of Continuous Fictitious Play, and offers an alternative to discretization. We complement our theoretical findings with experiments that demonstrate the effectiveness of the method.
Understanding the training dynamics of deep neural networks remains a major open problem, with physics-inspired approaches offering promising insights. Building on this perspective, we develop a thermodynamic framework to describe the stationary distributions of stochastic gradient descent (SGD) with weight decay for scale-invariant neural networks, a setting that both reflects practical architectures with normalization layers and permits theoretical analysis. We establish analogies between training hyperparameters (e.g., learning rate, weight decay) and thermodynamic variables such as temperature, pressure, and volume. Starting with a simplified isotropic noise model, we uncover a close correspondence between SGD dynamics and ideal gas behavior, validated through theory and simulation. Extending to training of neural networks, we show that key predictions of the framework, including the behavior of stationary entropy, align closely with experimental observations. This framework provides a principled foundation for interpreting training dynamics and may guide future work on hyperparameter tuning and the design of learning rate schedulers.
Convex clustering is a well-regarded clustering method, resembling the similar centroid-based approach of Lloyd's $k$-means, without requiring a predefined cluster count. It starts with each data point as its centroid and iteratively merges them. Despite its advantages, this method can fail when dealing with data exhibiting linearly non-separable or non-convex structures. To mitigate the limitations, we propose a kernelized extension of the convex clustering method. This approach projects the data points into a Reproducing Kernel Hilbert Space (RKHS) using a feature map, enabling convex clustering in this transformed space. This kernelization not only allows for better handling of complex data distributions but also produces an embedding in a finite-dimensional vector space. We provide a comprehensive theoretical underpinning for our kernelized approach, proving algorithmic convergence and establishing finite sample bounds for our estimates. The effectiveness of our method is demonstrated through extensive experiments on both synthetic and real-world datasets, showing superior performance compared to state-of-the-art clustering techniques. This work marks a significant advancement in the field, offering an effective solution for clustering in non-linear and non-convex data scenarios.
We introduce missingness-MDPs (miss-MDPs), a novel subclass of partially observable Markov decision processes (POMDPs) that incorporates the theory of missing data. A miss-MDP is a POMDP whose observation function is a missingness function, specifying the probability that individual state features are missing (i.e., unobserved) at a time step. The literature distinguishes three canonical missingness types: (1) missing completely at random (MCAR), (2) missing at random (MAR), and (3) missing not at random (MNAR). The problem is to compute near-optimal policies for a miss-MDP with an unknown missingness function, given a dataset of action-observation histories. Achieving such optimality guarantees for policies requires learning the missingness function from data, which is infeasible for general POMDPs. To overcome this challenge, we exploit the structural properties of different missingness types to derive probably approximately correct (PAC) algorithms for learning the missingness function. These algorithms yield an approximate but fully specified miss-MDP that we solve using off-the-shelf planning methods. We prove that, with high probability, the resulting policies are ε-optimal in the true miss-MDP. Empirical results confirm the theory and demonstrate superior performance of our approach over two model-free methods.
Decentralized Multi Agent Reinforcement Learning (MARL) faces a fundamental dilemma in real world deployments: agents must operate under epistemic fragmentation, where local observations are severely occluded, while navigating heterogeneous value landscapes, where sparse, critical events carry disproportionately high stakes. Existing paradigms typically decouple state estimation from policy optimization, guiding perception modules merely to minimize uniform reconstruction error. This leads to a Perception Value Misalignment, where agents squander computational resources reconstructing task irrelevant background noise while failing to resolve uncertainties in high value regions. To bridge this gap, we propose EVA-Gen (Epistemic Value Alignment via Generative Models) that establishes a cybernetic loop between generative perception and value based decision making. We formulate the Value Conditioned Reconstruction Paradigm, establishing that optimal perception under resource constraints is functionally weighted by the gradient of the value function. EVA-Gen couples Backward Flow to steer diffusion toward high stakes manifolds, Collaborative Information Bottleneck to filter communication for value relevant consensus, and Risk Sensitive Rectification to prevent sparse signal dilution, synergistically closing the perception control loop. Empirically, we demonstrate that EVA-Gen achieves superior performance in three value-heterogeneous multi agent environments.
Combining predictions from heterogeneous classifiers—such as in-house deep learning models, human experts, and large language models (LLMs)—is a key challenge, especially in data-scarce environments such as humanitarian operations. We propose a flexible Bayesian framework to effectively fuse these diverse inputs. By integrating classifier logits with auxiliary human feedback (e.g., confidence, image clarity) using an ordered probit process, our model generalizes prior work to accommodate the real-world properties of these classifiers. We validate our framework on a challenging product recognition task in food bank operations, an environment defined by data scarcity and an inexperienced volunteer workforce. Our combined model significantly outperforms standalone ResNet, human, and LLM-based approaches, demonstrating the practical benefits of fusing these heterogeneous signal sources.
Detecting hidden confounding is crucial for reliable causal analysis from observational data, directly determining which downstream causal inference method to be deployed. Inspired by the theory of higher-order regression, recent sample-efficient hypothesis testing strategies overcome the restrictive requirement of multiple heterogeneous data environment. Despite their progress on single-environment confounder detection, such methods suffer from intrinsic flaws that the structural functions of the causal models should be specified in prior (linear or specific kernel functions). By contrast, real-world data acquisition exhibits diverse, unknown forms of structural functions, imposing an important but challenging gap between theories of higher-order regressions to practical confounder detection. In this paper, we contribute a Bi-level Kernel Confounder Detection (BiKCD) framework by learning adaptive kernelized structural space of structural functions. Subsequently, our BiKCD constructs hypothesis testing by comparing coefficients from the higher-order regression and the classical ordinary least squares in learned kernelized space. Finally, the hypothesis is calibrated to ensure valid inference under adaptivity. Theoretically, we establish an oracle-type risk bound for the selected structural space over a candidate kernel family, with the Type-I error control for the downstream test. Extensive experiments on synthetic and real-world datasets demonstrate the effectiveness of the proposed BiKCD.
In this work, we propose the first constant-approximation algorithms, LinAst and LinAtg, which simultaneously achieve optimal query complexity O(n) and adaptive complexity O(log n) for non-monotone submodular maximization under a cardinality constraint k over a ground set of size n. Specifically, compared with existing algorithms that attain the best known adaptive complexity of O(log n), our approach preserves this adaptivity while reducing the query complexity from O(n log k) to O(n) and improving the approximation ratio from 0.172-epsilon to 0.193-epsilon. Our algorithms are built upon LinAdapt, which achieves a constant approximation ratio with O(log n) adaptive rounds and linear query complexity by requiring only O(1) candidate guesses of the optimal value. We further introduce the BoostAdapt algorithm, which improves the approximation guarantee to 0.25-\epsilon with O(log n log k) adaptive complexity and O(n log k) query complexity, based on a novel staggered greedy threshold framework that alternately constructs two disjoint solution sets over O(log k) sequential rounds. Extensive experiments on standard benchmark datasets demonstrate that our algorithms consistently outperform state-of-the-art methods in terms of solution quality, query complexity, and running time.
Fairness k-submodular maximization has attracted increasing interest due to its broad relevance in artificial intelligence and machine learning. However, most existing works are limited to monotone objectives or simple size constraints, while non-monotone settings with richer constraints remain largely unexplored. In this paper, we first introduce a constant-factor approximation algorithm for the problem with a general non-monotone objective function under a matroid constraint. Our approach is built upon a two-stage algorithmic framework. Specifically, we first develop an algorithm that guarantees feasibility with respect to upper fairness bounds only. We then show how this algorithm can be systematically extended to simultaneously enforce fairness bounds, while preserving provable approximation guarantees. Comprehensive experiments on standard benchmark datasets demonstrate that our algorithm achieves competitive objective values while maintaining a favorable balance between fairness guarantees and query complexity efficiency compared to existing state-of-the-art methods.
Parameter sharing is a central design choice in cooperative multi-agent reinforcement learning, yet it fundamentally conflicts with the need for role specialization in heterogeneous cooperative environments. Existing role-based methods typically learn monolithic role representations, which often suffer from gradient interference and fail to capture the compositional structure of complex behaviors. Inspired by Trait Theory, we propose DEcompose and COnstruct Roles (DECOR), a framework that models agent roles as dynamic compositions of orthogonal behavioral traits. DECOR introduces an orthogonal Mixture-of-Experts architecture to decompose behaviors into independent traits, mitigating destructive gradient interference under parameter sharing, and a group-consensus guided mechanism to extract team-level tactical intents that guide role composition.Experiments on multiple benchmarks demonstrate that DECOR consistently improves sample efficiency and overall performance over existing related methods.
We introduce QUINTIC, a general algorithm for actively learning quantitative automata from preferences. Quantitative automata evaluate input sequences by applying a valuation function---such as sum, product, or average---to the output labels of the states visited. Such models naturally arise in use cases ranging from probabilistic verification, sequence classification, and sequential decision making. However, existing learning approaches, such as variants of L*, weighted‐automata learning algorithms, and active learning preference‐driven methods, either assume finite output alphabets or restrict the valuation function to particular forms. QUINTIC utilizes a symbolic observation table and applies deductive reasoning with the assistance of an SMT solver to identify the correct minimal state, transition, and state label combination of the quantitative automaton. The deductive reasoning relies on the minimal combination of theories determined by the valuation function and output alphabet. Consequently, QUINTIC has completeness, minimalism, and query complexity guarantees, and learns quantitative automata across finite, integer, and rational outputs. Our extensive experiments show how QUINTIC scales under weak or strong feedback, and alternative MaxSMT objectives.
Real-world multi-agent systems, from traffic coordination to resource allocation, are often modeled as general-sum games where individual incentives conflict with collective welfare. In these settings, the central challenge is not merely finding an equilibrium, but selecting socially desirable outcomes among many suboptimal Nash equilibria. Standard deep multi-agent reinforcement learning (MARL) methods struggle with this problem, as value-decomposition approaches are constrained by monotonicity assumptions and policy-gradient methods often converge to stable but socially inefficient equilibria. To address this limitation, we propose Phi-Actor-Critic (Phi-AC), a framework that leverages swap regret minimization to steer learning toward high-welfare correlated equilibria (CE). To make counterfactual regret estimation tractable in deep MARL, Phi-AC employs a centralized attention critic that predicts vector-valued regrets in a single forward pass, avoiding computationally expensive counterfactual simulations. We further introduce a Lagrangian-based equilibrium selection mechanism that optimizes social welfare while enforcing stability through regret constraints. Experiments on matrix games, Multi-Agent Particle Environments (MPE), and the Melting Pot Harvest scenario demonstrate that Phi-AC learns efficient and stable coordination strategies across diverse mixed-motive settings while maintaining high collective return and competitive fairness.
We study the question of existence and fast computation of fair and efficient allocations of indivisible resources among agents with additive valuations. As such allocations may not exist for arbitrary instances, we ask if they exist for typical or random instances, meaning when the utility values of agents for the resources are drawn from certain distributions. In this paper, we extend the previously studied formal models of this problem to non-identical items. We assume that every item is associated with a distribution U_j, and every agent's utility value for the item is drawn independently from U_j. We show that envy-free fair and maximum social welfare efficient allocations exist with high probability in the asymptotic setting, meaning when the number of agents n and items m are large. Further, we show that when m = Ω(n log n), then by only sampling O(log m) or O((log m)^2) utility values per item instead of all the n, we can compute these allocations in Õ(m) time. Finally, we simulate our algorithms on randomly generated instances and show that even for small instances, we suffer small multiplicative losses in the fairness and efficiency guarantees and converge to fully optimal guarantees quickly.
Partial Dependence Plots (PDPs) visualize how changes in a single feature affect the average model prediction. They are widely used in practice to interpret decision tree ensembles and other machine learning models. Joint-PDPs extend this idea to pairs of features, revealing their combined effect. Partial Dependence Interaction Values (PDIVs) measure feature interactions. The Any-Order-PDIVs task computes these interactions for every feature subset across all rows of the dataset. We introduce WOODELF++, a unified and efficient approach for computing all these useful explainability tools on decision tree ensembles, building on WOODELF, an algorithm for efficient SHAP computation. By deriving suitable metrics over pseudo-Boolean functions, WOODELF++ can compute PDPs (exact and approximate), Joint-PDPs, and Any-Order-PDIVs in a unified framework. Our method delivers substantial complexity improvements over the state of the art, including an exponential gain for Any-Order-PDIVs. Additionally, we introduce and efficiently compute Full PDPs, which leverage the model’s split thresholds to faithfully capture its behavior across all possible feature values. WOODELF++ is implemented in pure Python and supports GPU acceleration. On a dataset with 400,000 rows, WOODELF++ computes PDP and Joint-PDP up to 6x faster than the state of the art and up to five orders of magnitude faster than scikit-learn. For Any-Order-PDIVs, the gap is even larger: WOODELF++ computes all interaction values in 5 minutes, while the state of the art is estimated to require over 1,000,000 years.
Low-Light Image Enhancement (LLIE) has long been a challenging problem in low-level vision, as insufficient illumination often leads to low contrast, detail loss, and noise. Recent studies show that deep learning-based Retinex theory can effectively decouple illumination and reflectance. However, existing methods frequently suffer from over-enhancement or color distortion, and often assume uniform noise or ideal lighting. To address these limitations, we propose InterLight, a novel framework that systematically excavates and operationalizes intrinsic illumination priors for LLIE. Our core insight is that robust enhancement requires not just estimating illumination, but constructing an illumination-aware pipeline. We first inject sensor-level illumination-response priors via physics-guided augmentation, then represent the degradation through adaptive prompts conditioned on the scene's latent illumination state. This explicit representation directly guides a luminance-gated intrinsic memory mechanism to selectively compensate for information loss, prioritizing reconstruction in dark regions while preserving fidelity in bright ones. Finally, the entire process is regularized by a self-supervised consistency objective that distills illumination-invariant features. By deeply exploiting intrinsic illumination priors, our method achieves clearer textures and more visually coherent enhancement results. Extensive experiments across multiple benchmarks demonstrate the effectiveness of our approach. Code is available at: https://github.com/House-yuyu/InterLight.
Multi-objective bandits with hierarchical preferences and safety constraints is central to many real-world decision-making tasks such as healthcare treatment planning and safe autonomous control, where multiple objectives must be optimized according to their priorities while ensuring safety requirements are satisfied. In this paper, we study a multi-objective stochastic linear bandit framework that incorporates hierarchical preferences together with safety constraints, requiring the learner to remain competitive with respect to a known baseline policy. We consider two practically motivated safety models: (i) cumulative constraints, which require the cumulative performance to exceed the baseline, and (ii) stage-wise constraints, which impose this requirement at each time step. We propose two algorithms, LexUCB-C and LexTS-S, designed for the cumulative and stage-wise settings, respectively. We establish regret bounds showing that both algorithms achieve performance comparable to existing single-objective safe linear bandit methods, while simultaneously optimizing multiple objectives. In addition to theoretical guarantees, we develop a carefully designed experimental framework that captures the interaction between hierarchical preferences and safety constraints. Experiments on synthetic and real-world datasets validate our theory and demonstrate the effectiveness of the proposed methods.
Bounded fitting is an attractive paradigm for learning logical formulas from labeled data examples that offers PAC-style generalization guarantees and can often be implemented leveraging SAT solvers. It has been successfully applied to learning concepts of the description logic ALC. We study bounded fitting for learning concepts in expressive description logics that extend ALC with inverse roles, qualified number restrictions, and feature comparisons. We investigate under which conditions bounded fitting keeps its favorable theoretical properties in this setting, and implement is using a SAT solver. We compare our implementation against state-of-the-art concept learners with encouraging results, demonstrating that it is a practical approach to expressive concept learning.
Subgame solving is a technique for scaling algorithms to large games by locally refining a precomputed blueprint strategy during gameplay. While straightforward in perfect-information games where search starts from the current state, subgame solving in imperfect-information games must account for hidden states and uncertainty about the opponent's past strategy. Gadget games were developed to ensure that the improved subgame strategy is robust against any possible opponent's strategy in a zero-sum game. Gadget games typically contain infinitely many Nash equilibria. We demonstrate that while these equilibria are equivalent in the gadget game, they yield vastly different performance in the full game, even when facing a rational opponent. We propose gadget game sequential equilibria as the preferred solution concept. We introduce modifications to the sequence-form linear program and counterfactual regret minimization that converge to these refined solutions with only mild additional computational cost. Additionally, we provide several new insights into the surprising superiority of the resolving gadget game over the max-margin gadget game. Our experiments compare different Nash equilibria of gadget games in several standard benchmark games, showing that our refined equilibria consistently outperform unrefined Nash equilibria, and can reduce the exploitability of the overall strategy by more than 50%.
Current self-evolution methods mostly chase recall, they learn from any trajectory that ends with the right answer, even when the path relies on a "lucky guess". Such reasoning appears valid in-distribution but often fails the moment the task shifts slightly. We argue that robust evolution implies Structural Invariance: a reasoning path is valid only if its core dependency graph remains isomorphic under counterfactual perturbations. I-EDI enforces this with Verifiable Counterfactual Simulation (VCS). Instead of treating data generation as mere "sample and filter," we treat it as an intervention. Unlike standard rejection sampling, VCS acts as a structural stress test: it accepts a reasoning trace only if it remains valid across generated counterfactuals (e.g., numerical perturbations, context shifts). While this strict filtering reduces the volume of training data (trading recall for precision), our experiments on MATH and GSM8K show it effectively prevents hallucination accumulation, achieving superior out-of-distribution generalization compared to baselines.