We initiate the study of single-sample bilateral trade with a broker, drawing an analogy to the setting of single-sample bilateral trade without a broker considered in [1] and [5]. Our model captures the three-sided interaction in which a broker mediates trade between a buyer and seller, each described by a valuation distribution from which a single sample can be drawn. We consider two settings in particular: one where the valuation distributions of the buyer and seller are identical and one where the valuation distributions are stochastically ordered. We analyze simple mechanisms that rely only on a single sample from each agent's distribution and show that these mechanisms achieve constant-factor approximations to the first-best gains-from-trade (GFT), first-best social welfare (SW), and optimal profit under the standard monotone-hazard-rate assumption. We then complement these results with matching or nearly matching upper bounds on the GFT and SW of our mechanisms. Notably, in both settings, we observe fairly small losses in the approximation factors to the first-best GFT and first-best SW due to the existence of the broker (benchmarked against the corresponding approximation factors in the setting without a broker). Furthermore, our results stand in stark contrast to those of [12], who show inapproximability results under a strategic broker with full distributional knowledge. Our results provide insight into the design of data-efficient brokerage mechanisms for online marketplaces and decentralized trading platforms, where intermediaries must facilitate trade under severe informational constraints. They highlight how even minimal data can enable robust and incentive-compatible brokerage in uncertain markets for both the broker and the market participants.
论文检索
输入标题、作者或关键词，从 2,877 篇学术成果中精准定位
Web3 technologies and decentralised finance (DeFi) have not only revolutionised finance, but they have also given rise to completely different concepts in terms of how we handle our wealth and how we utilise the Internet, which is still an unreliable medium for the exchange of information. To overcome trust issues, cryptographic tools were introduced and these days we even put our digital assets on the blockchain. These new technologies enabled us to make most financial solutions decentralised. A widely popular financial product that is implemented on blockchains is a constant product market maker (CPMM). A CPMM can be used to swap digital assets between mutually untrusting parties by relying on prices calculated from its bonding curve. A blockchain-based automated market maker (AMM) quotes prices that usually lag behind external market prices, and this price difference can be exploited by automated bots, aka. arbitrageurs. The question we investigate in this work focuses on this issue. More specifically, we experiment with different approaches from financial mathematics to account for stochastic price changes, perform extensive measurements to quantify the characteristics of the DeFi market, focusing on mainnet Ethereum and develop stochastic grid optimisers to fit model parameters to actual AMM market data that we extract from the logs of the Ethereum virtual machine. We report on model performance that is more aligned with reality compared to previous works that have relied on naive two-parameter Black-Scholes (BS) models. Our results reveal that hidden Markov models can give better estimates for both the number of arbitrage trades and the arbitrage profits when combined with a jump diffusion model and a two-parameter BS model.
Active feature acquisition (AFA) studies how a predictive system can sequentially choose which feature values to obtain for each instance to balance predictive accuracy against feature acquisition cost. This survey provides the first unified treatment of modern AFA through a partially observable Markov decision process (POMDP) formulation, showing that most existing methods can be understood as different approximations of the same underlying sequential decision problem. The survey proposes an up-to-date taxonomy organizing AFA into four categories: (i) embedded cost-aware predictors (notably cost-sensitive decision trees and ensembles), (ii) model-based methods that plan using learned probabilistic components, (iii) model-free methods that learn acquisition policies from simulated episodes, and (iv) hybrid methods that combine the strengths of model-based and model-free approaches. We argue that this POMDP-centric view clarifies connections among existing methods and motivates more principled algorithm design. Since much prior work is heuristic and lacks formal guarantees, we also outline routes to guarantees by connecting AFA to adaptive stochastic optimization. We conclude by highlighting open challenges and promising directions for future research.
In many real-world scenarios, interactions happen in a group-wise manner with multiple entities, and therefore, hypergraphs are a suitable tool to accurately represent such interactions. Various generative models have been proposed to explore fundamental mechanisms underlying hyperedge formation. However, most existing models do not account for node attributes, which can play a significant role in hyperedge formation. As a result, they fail to capture the interactions between structure and node attributes. To address this issue, we propose NoAH, a stochastic hypergraph generative model for attributed hypergraphs. NoAH utilizes the core–fringe node hierarchy to model hyperedge formation as a series of node attachments and determines attachment probabilities based on node attributes. We further introduce NoAHFit, a parameter learning procedure for fitting NoAH to a given real-world hypergraph. Through experiments, we show that NoAH with NoAHFit more accurately reproduces the structure–attribute interplay than baseline hypergraph generative models. Our code, supplementary materials, and datasets are provided at https://github.com/jaewan01/NoAH.
Recently, we are witnessing an increase in computation power and memory, leading to strong AI algorithms becoming applicable in areas affecting our daily lives. We focus on AI planning solutions for complex, real-life decision-making problems under uncertainty, such as autonomous driving. Human trust in such AI-based systems is essential for their acceptance and market penetration. Moreover, users need to establish appropriate levels of trust to benefit the most from these systems. Previous studies have motivated this work, showing that users can benefit from receiving (handcrafted) information about the reasoning of a stochastic AI planner, for example, controlling automated driving maneuvers. Our solution to automating these hand-crafted notifications with explainable AI algorithms, XAI, includes studying: (1) what explanations can be generated from an AI planning system, applied to a real-world problem, in real-time? What is that content that can be processed from a planner's reasoning that can help users understand and trust the system controlling a behavior they are experiencing? (2) when can this information be displayed? and (3) how shall we display this information to an end user? The value of these computed XAI notifications has been assessed through an online user study with 800 participants, experiencing simulated automated driving scenarios. Our results show that real time XAI notifications decrease significantly subjective misunderstanding of participants compared to those that received only a dynamic HMI display. Also, our XAI solution significantly increases the level of understanding of participants with prior ADAS experience and of participants that lack such experience but have non-negative prior trust to ADAS features. The level of trust significantly increases when XAI was provided to a more restricted set of the participants, including those over 60 years old, with prior ADAS experience and non-negative prior trust attitude to automated features.
Riemannian optimization has attracted increasing attention recently as it is related to a variety of machine learning problems, including principal component analysis, dictionary learning, and mixture modeling. To tackle modern large-scale machine learning tasks, distributed learning is usually considered as an effective solution that trains a global model over multiple worker nodes collaboratively to enhance the computational power. Centralized learning and decentralized learning are two types of distributed learning. Centralized learning employs a central parameter server to coordinate the training process while in decentralized learning, each worker only communicates with its peer neighbors. In this paper, we propose accelerated distributed Riemannian stochastic gradient descent algorithms with random shuffling in the cases of both centralized and decentralized learning. We improve the stochastic first-order oracle complexity of the Riemannian SGD from to where is the size of training data. We conduct an experiment of the leading eigenvector problem under the condition of centralized learning and decentralized learning to validate the performance of our methods.
In many multi-agent applications, tasks yield rewards only when executed by a coalition meeting an unknown size threshold; otherwise, feedback is fully censored. This censorship creates an identifiability problem: agents cannot distinguish stochastic failure from insufficient coordination. We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) and analyze it under both centralized and decentralized coordination. We show that a centralized algorithm (C-TAC) achieves cumulative regret O(log T), decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation. We then introduce D-TAC, a decentralized event-triggered protocol in which agents synchronize only when their structural beliefs change. Empirically, D-TAC achieves a 23x reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative belief fusion. These results characterize the coordination cost of learning under censored feedback and show that near-centralized communication efficiency is achievable without continuous synchronization.
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.
Achieving optimal coordination in multiagent systems involves a trade-off between intractable centralized planning and suboptimal decentralized execution. We bridge this gap by introducing Approximate Recursive Small Step-Semi-Decentralized A* (RS-SDA*), a tree search algorithm that exploits time-varying centralization during periods of available communication conditioned on the environment or joint actions. By interleaving offline planning with online search and using relaxed heuristics, RS-SDA* achieves high solution quality with reduced computational overhead. SDec-POMDP benchmark experiments show that Approximate RS-SDA* often finds near exact optimal solutions in less than 1% of the time required by exact algorithms. We show scalability in six labyrinth environments both deterministic and stochastic state transitions, and demonstrate real-world feasibility with a multi-drone search-and-rescue simulation in the DARPA Subterranean Challenge cave system.
Reinforcement learning (RL) is commonly used to learn reward-optimizing policies. However, RL policies are not always trained with ethical behavior in mind, which can lead an agent to violate social or legal norms in pursuit of its goal. Retraining agents with additional norms is not always feasible, especially in complex stochastic environments. To mitigate this issue, we present a probabilistic policy fixing framework that adapts norm-agnostic policies online. Using Answer Set Programming (ASP), we generate policy fixes that minimize deviations from the RL policy while optimizing for norm adherence against a set of sampled worlds. Based on the Rule of Three and Hoeffding's inequality, we provide guarantees that fixed policies are near optimal, given a specified level of confidence.
This paper addresses the problem of learning to sparsify stochastic linear bandits, where a decision-maker sequentially selects actions from a high-dimensional space subject to a sparsity constraint on the number of nonzero elements in the action vector. The key challenge lies in minimizing cumulative regret while tackling the potential NP-hardness of finding optimal sparse actions due to the inherent combinatorial structure of the problem. We propose an adaptively phased exploration and exploitation algorithmic framework, utilizing ordinary least squares for parameter learning and specialized subroutines for sparse action selection. When the action set is a Euclidean ball, optimal sparse actions can be efficiently computed, enabling us to establish a Õ(d √T) regret, where d is the dimension of the action vector and T is the time horizon length. For general convex and compact action sets where finding optimal sparse actions is intractable, we employ a greedy subroutine. For general strongly convex action sets, we derive a Õ(d √T) α-regret; for general compact sets lacking strong convexity, we establish a Õ(d T^(2/3)) α-regret, where α pertains to the approximation ratio of the greedy algorithm. Finally, we validate the performance of our algorithms using extensive experiments.
Accurately predicting the popularity of information cascades facilitates the development of social media network applications. During the cascade propagation process, user-generated comments continually evolve, thereby substantially affecting overall information popularity. However, existing methods primarily focus on learning structural–temporal cascade dynamics while neglecting the modeling of user-generated comment evolution, leading to suboptimal predictions. In this paper, we propose a novel framework, CasUGC, that aligns Cascade dynamics with User-Generated Comment evolution for popularity prediction. Specifically, we develop a dual-granularity alignment strategy that bridges the representation gap between comment semantics and structural–temporal dynamics at both the user and cascade levels. Building on this alignment, we further design a dynamic cascade feature generation module to produce temporally enhanced cascade embeddings. To further address the inherent uncertainties in both alignment and prediction, we introduce two diffusion-based components: a cascade-level diffusion network that learns a latent distribution mapping between semantic and structural–temporal representations, and a second diffusion process that captures the stochasticity of propagation dynamics for robust prediction. Extensive experiments conducted on four real-world social media datasets demonstrate the superiority of CasUGC over state-of-the-art methods.
Denoising Diffusion Codebook Models (DDCM) have emerged as a promising framework for zero-shot image compression by replacing stochastic sampling with discrete selection from a reproducible Gaussian codebook. By greedily picking noise vectors that best match the target image, DDCM encodes the generative trajectory into a compact sequence of indices for image compression. However, the target-guided noise selection provides only coarse guidance as the discrepancy between the denoiser's output and the target image is substantial. This discrepancy inevitably results in trajectory drift, necessitating massive codebooks to span the enlarged search space and extensive inference steps to gradually compensate for the deviation. In this paper, we propose the Trajectory-Consistent Diffusion Codebook Model (TC-DDCM) to address these inefficiencies. Rather than approximating the distant target, TC-DDCM navigates the generative process by strictly tracking a pre-computed inversion trajectory. This paradigm shift yields two critical advantages: 1) By minimizing the deviation to the proximal reference state along the trajectory, the search space is drastically shrunk, resulting in significantly smaller codebooks. 2) By aligning the generative steps with inversion methods, TC-DDCM achieves optimal reconstruction in a few inference steps. Extensive experiments demonstrate that TC-DDCM significantly outperforms state-of-the-art zero-shot methods in rate-distortion-perception performance at ultra-low bitrates, making zero-shot diffusion-based compression practical.
Supervised infrared-visible image fusion (IVIF) often overfits limited training distributions, creating a critical generalization gap under open-world degradations (rain, haze, low light, noise, blur). To address this issue, we propose AIR-Fusion, a parameter-efficient adaptation of a frozen, restoration-capable latent diffusion backbone for degraded IVIF without full fine-tuning, transferring restoration priors for robust fusion. A Cross-Modal Bridging Adapter (CMBA) aligns infrared cues and textual instructions with the frozen diffusion conditioning space and injects them into multi-scale denoising features to steer instruction-guided restoration-aware fusion. In addition, a Trajectory-Constrained Rectifier (TCR) regularizes stochastic sampling via a pixel-latent closed loop, rectifying intermediate predictions with source-referenced structures and re-encoding them to stabilize the denoising trajectory and recover fine details suppressed by latent compression. Experiments across multiple datasets and degradation settings show consistent improvements in restoration quality and fusion fidelity, with strong generalization under complex and compounded degradations.
We study influence maximization in general stochastic models, the observed cascades model, and the independent cascade (IC) model. For general stochastic models with only black-box sample access, we introduce a low-adaptivity optimization framework that improves sample complexity and running time over the prior work and is instrumental to all our results. We further introduce an adaptive algorithm guided by empirical variance, avoiding pessimistic worst-case bounds. Combining our optimization framework with sketching, we obtain the first algorithm with provable guarantees and nearly-linear running time for influence maximization on observed cascades, optimal up to logarithmic factors. For IC, we prove a novel tail bound replacing a factor n with 𝜏 (the number of diffusion steps) in sample complexity, improving over prior work when 𝜏 is small, as is common due to small-world phenomena. Experiments confirm substantial speedups while maintaining solution quality.
Joint optimization of pricing, dispatching, and routing is critical for hub-based mobility services but challenging due to complex decision couplings and strict service guarantees, such as Order Response Rate (ORR). Conventional constrained reinforcement learning often struggles in this mixed continuous--combinatorial action space, suffering from oscillatory behavior in Lagrangian dual variables and unstable constraint satisfaction. To address this, we propose PID-SACA, a unified framework that integrates an entropy-regularized actor--critic policy for continuous pricing and dispatching assisted by an embedded routing solver for execution-aware feedback. Crucially, we adapt the PID control mechanism to the Lagrangian dual update process. This approach leverages proportional, integral, and derivative feedback to dampen oscillations caused by stochastic gradient variance, ensuring robust long-term constraint enforcement. We provide theoretical analysis on the boundedness of dual variables, and experiments on publicly available large-scale mobility datasets demonstrate that PID-SACA significantly outperforms baselines, achieving high revenue with stable service compliance. Code: https://github.com/jerry0375/PID-SACA
In many real-world scenarios, agents operate across heterogeneous environments where the underlying dynamics and data-generating processes vary. Standard reinforcement learning and imitation learning methods often fail in such settings as they typically assume stationarity and learn policies that overfit to environment-specific correlations. A key challenge is the presence of spurious correlations as observed states often contain both causal and non-causal features, with the latter introducing environment-specific biases that undermine generalization. To address this problem, we propose DropConnect-based Causal Imitation Learning (DCIL), a novel offline imitation learning framework designed to identify and exploit stable causal mechanisms across diverse environments. DCIL introduces a gradient alignment constraint that encourages the policy to align with causal structures shared across training environments. To further mitigate overfitting to spurious correlations, DCIL involves DropConnect-based regularization, injecting stochastic perturbations into network weights to simulate parameter uncertainty and reduce reliance on unstable features. We evaluate DCIL on synthetic benchmarks derived from OpenAI Gym control tasks, where non-causal features exhibiting spurious correlations are explicitly injected to simulate environmental heterogeneity. Experimental results show that DCIL outperforms state-of-the-art imitation learning baselines, achieving superior generalization to unseen environments. These findings highlight the importance of incorporating causal reasoning and structured regularization into policy learning for robust performance under environment shift.
Survival models on networks describe the time-evolving dynamics of complex systems, but existing frameworks suffer from two key limitations: First, many past approaches implicitly assume independent censoring, which can introduce substantial bias. Second, point-process-based models often emphasize only sending behavior and overlook shared latent structure between interacting nodes. Recent work has incorporated copulas into deep survival models to mitigate censoring bias, but these methods do not capture topological role structure. Another line of research combines survival analysis with the Mixed-Membership Stochastic Blockmodel (MMSB) to model heterogeneity via role-specific hazard rates; however, it typically assumes structural independence and therefore misses important correlations between roles. To bridge these gaps, we apply an improved Copula–MMSB mechanism and propose the first Survival Fully-Collapsed Copula Mixed Membership Blockmodel. Our framework jointly models time-to-event dynamics and complex dependencies among latent roles. On the Enron benchmark, it surpasses state-of-the-art survival blockmodels in both predictive likelihood and structural interpretability. Additionally, the model admits an exact closed-form discrete distribution over role pairs, which enables a fully collapsed Gibbs sampler and avoids the slow mixing and poor convergence common in non-conjugate inference. In simulations, this yields a 100× improvement in sampling efficiency over semi-collapsed baselines.
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.
The Dynamic Flexible Job Shop Scheduling Problem (DFJSP) necessitates a trade-off between instant reaction to stochastic disturbances and global optimization of production goals. Conventional priority rules are insufficiently flexible to handle complex disruptions, whereas learning-based approaches often compromise interpretability or fail to generalize across problem scales. Although Large Language Models (LLMs) offer advanced reasoning capabilities to bridge this gap, their substantial inference latency is incompatible with the millisecond-level decision cycles of industrial control systems. To resolve this conflict, we introduce RACE-Sched, an asynchronous agent-based framework that decouples policy execution from logical reasoning via a dual-stream architecture. The Reactive Stream executes low-latency symbolic heuristics to enable real-time dispatching, while the parallel Deliberative Stream leverages an LLM to synthesize, validate, and evolve these rules. Candidate rules undergo rigorous testing in a sandbox and are deployed via atomic updates, ensuring safety without blocking the control loop. Additionally, a semantic rule repository indexes validated heuristics for retrieval-based initialization which enhances transferability across problem scales. Extensive evaluations on GEN-Bench, MK-Bench, and JMS-Bench demonstrate that RACE-Sched outperforms leading Deep Reinforcement Learning and other LLM-based baselines. This approach harmonizes real-time constraints with long-horizon reasoning to achieve superior solution quality and robust adaptation to dynamic events.