Computer Science & Mathematics

We study the minimax regret rate for episodic kernel-based reinforcement learning, where the expected reward and transition density belong to a Sobolev reproducing kernel Hilbert space, with continuous state and action spaces, and adversarial initial states. For Sobolev smoothness parameter $ν>0$, state dimension $d_S$, and action dimension $d_A$, we prove that the minimax expected regret over $T$ episodes is $\widetildeΘ(T^{\max\{e_A,e_B\}})$, where $e_A=\frac{ν+d_A}{2ν+d_A}$, $e_B=\frac{ν+d_A+3d_S/2}{2ν+d_A+2d_S}$ with the other model parameters fixed. The two exponents reflect the distinct difficulties of action selection and learning across states. We introduce Sobolev Optimal Value Iteration (SOVI), which attains this rate from observed rewards and transitions. For fixed smoothness and reference-kernel lengthscale, its regret bound has a prefactor polynomial in the state-action dimension $d=d_S+d_A$, horizon $H$, transition and reward RKHS norm bounds $u,B_r$, and kernel norm-comparison factor $Λ$, up to logarithmic factors. The algorithm separates initial action selection from continuation-value estimation and combines local polynomial approximation with the shared RKHS structure of the approximation errors. Our matching upper and lower bounds determine the optimal dependence on the number of episodes for Sobolev kernel-based reinforcement learning. Thus, we partially address the open problem in Vakili(2024) under the condition of the Sobolev kernel setup.

Modern system-on-chip (SoC) floorplanning is increasingly challenged by highly coupled complex design constraints. Existing methods often relax constraints into objectives via multi-objective optimization, leading to infeasible solutions or degraded quality. To address this, we formulate the problem as a constrained optimization task and propose a novel three-stage analytical framework integrating semidefinite programming (SDP), augmented Lagrangian method (ALM), and second-order cone programming (SOCP), which enforces constraints more rigorously and achieves higher-quality solutions. First, we adopt a two-step SDP formulation to obtain a robust initialization in the non-convex search space. Next, we incorporate differentiable objectives and constraints into an incremental ALM to jointly handle coupled design constraints during global floorplanning. Finally, an SOCP-based legalization strictly enforces feasibility while further reducing area. Experiments on the FloorSet benchmark show that our method satisfies all constraints with the fastest runtime. Compared with state-of-the-art methods, it reduces wirelength and area by 90\% and 16\% on average, and achieves near-optimal results, with wirelength and area being merely 2\% and 1\% larger than the ground-truth references, respectively.

Galaxies hosting strongly misaligned stellar and gas structures offer a direct window into external accretion and the buildup of angular momentum through multiple spin components. Such polar-structure systems are intrinsically rare and, until now, have been identified almost entirely at low redshift. The Euclid Quick Data Release (Q1), with its uniform, space-based VIS imaging, provides an unprecedented opportunity to locate these objects over wide areas and at much greater distances. We present the first visual search for polar-structure galaxy (PSG) candidates in Euclid VIS data, spanning approximately 10% of the Q1 survey footprint. This search yields the largest high-redshift PSG candidate sample assembled to date, including roughly 100 high-confidence systems with over 50 at $z \gtrsim 0.3$, along with additional populations of face-on rings and polar tidal structures (PTS). Robust candidates are detected out to redshifts of $z\sim1$, demonstrating that polar structures can be identified well beyond the local Universe. Although the present sample is not yet sufficient for quantitative occurrence rate or evolutionary measurements, it enables initial classification and basic structural characterization of PSGs at intermediate redshift. These results lay the groundwork for future statistical studies with forthcoming Euclid data releases and illustrate Euclid's power for rare-object science across cosmic time.

Robot tasks require grounding spatial language in physical scenes, but task success alone cannot establish whether spatial instructions are followed. We present BEHAVIOR-Spatial, a benchmark built on BEHAVIOR-1K that measures spatial question answering, point-based target grounding, and robot action to examine how VLM spatial understanding relates to VLA behavior. It comprises 3,256 spatial questions across 49 activities, 1,240 grounding queries across 14 manipulation tasks, and action evaluations covering those 14 tasks and 10 navigation tasks. Our manipulation protocol evaluates held-out configurations and instruction following when the requested target changes within a fixed training layout. The baseline achieves 41.6% on held-out configurations but only 16.1% under changed instructions. VLM adaptation and robot-data pretraining provide limited improvements, whereas oracle visual target cues raise these rates to 60.3% and 38.0%, respectively. Perception evaluations reveal policy-dependent correlations between VLM question-answering and grounding accuracy and VLA manipulation performance. Together, these findings motivate evaluating spatial instruction following alongside task completion and examining when spatial perception performance translates into robot behavior. Project website: https://arielchen07.github.io/behavior-spatial/.

One of the fundamental differences between biological neural networks and artificial neural networks (ANNs) is that biological neurons obey Dale's principle: each neuron projects either exclusively excitatory or exclusively inhibitory outputs. While this constraint is central to biological circuits, previous attempts to impose Dale's principle in ANNs have often led to training instability or degraded performance. In this work, we introduce EISep RNN, a recurrent neural network architecture that implements Dale's principle through a learnable excitatory-inhibitory separation. Across a series of learning settings, including multi-task learning, continual learning, and reinforcement learning, EISep achieves more stable training dynamics, competitive or improved performance, and sparser, more modular connectivity than vanilla RNNs and previous Dale-constrained models. EISep also exhibits stable and informative latent dynamics. These results establish Dale's principle as a biologically grounded and computationally effective inductive bias for recurrent neural networks.

This paper proposes a command-aligned sampling distribution that incorporates navigation commands directly into the exploration process to improve the efficiency of sampling-based motion planning for quadcopters in three-dimensional environments. Inspired by the Language-Aided Subset Sampling Motion Planner, this paper extends command-aware subset sampling to aerial systems. Subset sampling is generalized to command-aligned regions, enabling structured 3D exploration while preserving probabilistic completeness. Natural language instructions are grounded into yaw-conditioned and altitude-aware geometric constraints using a prompt-based large language model for entity extraction and instruction validation. Extensive simulations in complex environments demonstrate that the proposed method generates collision-free, consistent trajectories while significantly reducing sampling effort compared to uniform RRT-based planners.

Transformers achieve strong performance across modalities but are bottlenecked by the quadratic cost of attention. Sparse attention can reduce this cost, but effective sparsity must preserve useful long-range communication and map well to GPU hardware. We introduce INTRA--Interleaved Non-contiguous Token spaRse Attention--a hardware-aware static sparse attention design based on a relay-communication view under Computational Query Set (CQS) constraints. Rather than directly covering all token-to-token interactions within each sparse layer, INTRA uses complementary sparse groups to provide short mediated communication paths across layers. Scatter forms relay groups that sample broadly across local neighborhoods, while Gather reconnects these groups in subsequent layers. Under a partition model, this structure guides CQS-compatible sparse patterns with global reachability. Our CQS-aware FlashAttention-style kernel computes structured indices at runtime, loads selected non-contiguous tokens, and packs them densely for computation. On an A100, INTRA achieves a $1.53\times$ speedup in $2K$ FLUX.1-dev generation, with better measured image quality than evaluated CLEAR configurations after LoRA self-distillation. On LLaMA-3.1-8B, it improves long-context prefill efficiency with strong teacher-forced retrieval performance under matched LoRA adaptation. Attention-only benchmarks further show up to $8.4\times$ and $10.4\times$ speedups over MoBA and density-constrained NSA, respectively.

Swarm robotics enables scalable inspection through collective perception, where robots infer environmental properties from distributed observations. A common benchmark considers robots exploring black-white tiled environments and determining the majority tile type. While most work studies static environments, dynamic environments remain underexplored. We study collective perception in dynamic environments where the tile proportion and the spatial correlation of surface patterns may change over time. To enable implementation on resource-constrained robots, we integrate a lightweight change detection mechanism into a Bayesian collective decision-making framework that resets robot beliefs when distribution shifts are detected. The proposed detector requires constant memory and constant per-sample computation, unlike two recent competitive approaches that store the full sample stream, making it suitable for memory-constrained robots. We further introduce a method that detects spatially correlated sampling and adapts sampling intervals online to mitigate correlation effects. Our simulation results in Webots show competitive change detection delays, more consistent precision across communication settings, and improved decision accuracy under changing spatial correlations.

Construction robots operating near workers require navigation that can anticipate human motion while remaining robust to dynamic and unstructured site conditions. However, existing social navigation methods depend on hand-crafted interaction rules, labeled demonstrations, or robot-specific control policies, limiting their scalability and transferability in construction environments. We propose a real-time, LiDAR-only framework that learns interaction-aware path corrections from unlabeled demonstrations. Constant-velocity extrapolation generates residual learning targets, while a GNN models relationships among the robot, pedestrians, and goal context. During deployment, an extended Kalman filter tracks LiDAR detections to construct dynamic graphs, and the GNN offsets planner-generated waypoints through a planner-agnostic interface. Within the bricklaying trial, the GNN reduced path irregularity by 39.2\% and increased minimum TTC. Across Dynablox sequences, it increased minimum TTC by 38.3\% while producing shorter, smoother paths than the baselines. Ablation studies supported a 1.0-s prediction interval and confirmed the benefits of target context, reflection augmentation, and feature normalization.

Frontier agentic systems are capable of taking misaligned actions that may cause significant harm. Monitoring techniques are developed to oversee these systems in order to detect and prevent dangerous actions. However, current state-of-the-art monitors suffer from four persistent failure modes: complete detection failures, partial detections, accepting false benign framings, and suspicion score calibration errors. These failure cases can be efficiently combated by augmenting transcripts with supplementary hints, spanning command provenance, security-sensitive action flags, and task-disallowed effect markers. Provenance links allow for the recognition of diffuse attacks, while security and authorization flags simultaneously enable subtle attack recognition and provide an explicit reason for monitors to doubt the false benign framings they encounter, reducing rationalization and improving calibration. We find that augmenting weak extract-and-evaluate monitors with these hints significantly boosts performance with minimal computational cost. Furthermore, a failure mode analysis confirms that hints can remediate all four failure modes, notably almost entirely eliminating detection failures. A series of ablation studies emphasizes the efficiency and potential of the augmented extract-and-evaluate approach. Synthesizing our findings, we propose a tractable two-pronged approach toward enabling weak-to-strong monitoring.

Graph-signal estimation is commonly designed assuming that the underlying topology is known. In this paper, we consider estimation from general nonlinear measurements when the active topology is latent but is known to belong to a given family of candidate graphs. We first develop a class of topology-blind graph-spectral estimators that jointly exploit the candidate graphs, and characterize the performance loss compared to unconstrained linear estimation. We derive the minimum-mean-squared-error (MSE) multi-basis estimator and show that its optimal operator is the weighted projection of the topology-blind linear MMSE (LMMSE) operator onto the multi-graph filter space. This characterization provides exact expressions for the excess MSE and conditions for attaining the topology-blind LMMSE. To reduce the number of parameters, we develop estimators based on shared spectral responses and low-rank representations, and consider data-dependent estimators that infer the topology from the measurements, by maximum a-posteriori probability (MAP) selection or posterior weighting (multiple-model). We further extend the framework to networks of different sizes by jointly optimizing a common spectral function. We derive its MSE-optimal coefficients and decompose the resulting estimation loss into graph-filter approximation error and the additional cost of sharing a spectral response across networks. The proposed estimators admit sample-based implementations, while the shared spectral function can be applied to unseen graphs without retraining its coefficients. Simulations on IEEE power networks demonstrate the benefits of the proposed graph-spectral estimators under topology uncertainty and cross- network transfer.

Memory is increasingly used in long-horizon agents, yet the net value of building memory over direct retrieval from raw history remains largely unclear. Through a large-scale evaluation across multiple benchmarks and model backbones, we find many dedicated memory systems underperform naive RAG in many cases, indicating a negative net value. Taking RAG as a reference, we dissect the net value of memory into the gains and losses over direct retrieval, termed memory benefit and memory tax. These gains and losses arise because memory process changes how the raw information is organized and accessed. We view such changes as the double-edged deviations from the raw history. They are originally designed and introduced to benefit the task, for example by reorganizing facts or distilling preferences, but some may also remove or obscure evidence, giving rise to memory tax. Since memory benefit reflects the expected gains of its design, we then focus more on the overlooked memory tax, study how it arises from the system and evaluation side, and generalize the concept to more application scenarios of memory. We hope the notion of memory tax can provide a new lens and shift more attention from standalone performance to the net value of memory, informing more reliable memory designs and evaluations. We will open-source the code and results to the community. Project Page: https://hexuan21.github.io/MemoryTax/

Jailbreak benchmarks test one checkpoint and treat which jailbreaks break it as a property of its pretraining data and safety training. We ask whether another pretraining run of the same data, given the same safety training, would break on the same jailbreaks. For each of 25 pretraining data recipes, we take 1B base models from 3 pretraining seeds and give each the same safety post-training with 2 post-training seeds, for 150 models in all. We then collect 20 responses from every model to a shared set of jailbreak prompts and correlate the per-prompt non-refusal rates between every pair of models. On average, two post-trained copies of the same pretraining run have per-prompt non-refusal rates that correlate at 0.984. A different pretraining seed lowers the correlation to 0.811, and a different data recipe lowers it only slightly further, to 0.779. These results indicate that which jailbreaks break a checkpoint depends much more on its pretraining run than on its data, a pattern that holds in all 25 data recipes and at 150M and 300M parameters. In practice, the best of 91 attack templates found on one checkpoint stays the best after a new pretraining seed in only 27% of model pairs, against 67% after a new post-training seed. Each pretraining run also leaves a fingerprint: across 3,211 prompts, a model's per-prompt non-refusal rates identify its pretraining run among all 75 runs every time, and a random subset of 50 prompts still does so 98% of the time.

Special-science explanations often concern distributions rather than individual outcomes. Since higher-level states depend on lower-level processes, what would make a higher-level explanation redundant? I argue that redundancy requires replacement without loss, not merely a reconstruction of individual outcomes. Distributional counterfactual dependence (DCD) identifies how changes in higher-level conditions alter an outcome distribution or a relevant feature of it. Against the background of stochastic supervenience, I distinguish this explanatory role from the dependence of higher-level states on lower-level bases. A replacement must be specified independently of the distribution to be explained and preserve the same counterfactual pattern at the grain and across the conditions relevant to the question. Applications to wage distributions, cognitive load, and selection clarify this requirement. A hypothetical comparison shows how a lower-level model can preserve the explanation and why matching selected outcome statistics may not suffice. DCD thus describes one form of non-reductive explanation that depends on counterfactual organization rather than additional higher-level productive powers.

This paper studies the joint scheduling of nurses and hospital service robots as a bi-objective mixed-integer linear programming problem. The formulation represents heterogeneous nursing skills, alternative skill-coverage modes, nurse availability and temporal rules, workload balance, robot task capability, charging and battery dynamics, and human supervision. Robot workload relief is credited only when an eligible service is actually executed, and explicit supervision-load variables deduct the corresponding nurse capacity from clinical coverage. The receding-horizon formulation also includes a cross-window night--morning constraint and a terminal battery reserve. The computational study is presented as numerical verification on synthetic hospital-like instances rather than clinical validation. Under the proposed formulation, the eight-nurse reference case gives $Z_1=0.78$ and $Z_2=3.164$. A common-budget comparison on B20 seed~1 yields total shortage $53.70$ for the integrated model, compared with $58.03$ for sequential nurse--robot scheduling and $59.46$ for the nurse-only baseline. Additional experiments examine multiple epsilon budgets on a larger B30 instance, sensitivity to robot-relief/supervision parameters and objective weights, and one-day versus two-day rolling horizons against a static full-horizon reference. The battery and routing representations remain aggregate planning approximations, and the scalability evidence is interpreted accordingly. No patient records or real hospital staff data are used, so the results establish model behavior and comparative numerical evidence rather than practical clinical effectiveness.