Prompt-based offline methods are commonly used to optimize large language model (LLM) responses, but evaluating these responses is computationally intensive and often fails to accommodate diverse response styles. This study introduces a novel online evaluation framework that employs a multi-agent conversational bandit model to select optimal responses while aligning with user preferences dynamically. To tackle challenges such as high-dimensional features, large response sets, adaptive conversational needs, and multi-device access, we propose MACO, Multi-Agent Conversational Online Learning, which comprises two key components: (1) MACO-A: Executed by local agents, it employs an online elimination mechanism to filter out low-quality responses. (2) MACO-S: Executed by the cloud server, it adaptively adjusts selection strategies based on aggregated preference data. An adaptive preference mechanism triggers asynchronous conversations to enhance alignment efficiency. Theoretical analysis demonstrates that MACO achieves near-optimal regret bounds, matching state-of-the-art performance in various degenerate cases. Extensive experiments utilizing Google and OpenAI text embedding models on the real-world datasets with different response styles, combined with Llama and GPT-4o, show that MACO consistently outperforms baseline methods by at least 8.29% across varying response set sizes and numbers of agents.

The contextual multi-armed bandit (MAB) problem is crucial in sequential decision-making. A line of research, known as online clustering of bandits, extends contextual MAB by grouping similar users into clusters, utilizing shared features to improve learning efficiency. However, existing algorithms, which rely on the upper confidence bound (UCB) strategy, struggle to gather adequate statistical information to accurately identify unknown user clusters. As a result, their theoretical analyses require several strong assumptions about the "diversity" of contexts generated by the environment, leading to impractical settings, complicated analyses, and poor practical performance. Removing these assumptions has been a long-standing open problem in the clustering of bandits literature. In this work, we provide two partial solutions. First, we introduce an additional exploration phase to accelerate the identification of clusters. We integrate this general strategy into both graph-based and set-based algorithms and propose two new algorithms, UniCLUB and UniSCLUB. Remarkably, our algorithms require substantially weaker assumptions and simpler theoretical analyses while achieving superior cumulative regret compared to previous studies. Second, inspired by the smoothed analysis framework, we propose a more practical setting that eliminates the requirement for i.i.d. context generation used in previous studies, thus enhancing the performance of existing algorithms for online clustering of bandits. Extensive evaluations on both synthetic and real-world datasets demonstrate that our proposed algorithms outperform existing approaches.

Conversational recommender systems proactively query users with relevant ''key terms'' and leverage the feedback to elicit users' preferences for personalized recommendations. Conversational contextual bandits, a prevalent approach in this domain, aim to optimize preference learning by balancing exploitation and exploration. However, several limitations hinder their effectiveness in real-world scenarios. First, existing algorithms employ key term selection strategies with insufficient exploration, often failing to thoroughly probe users' preferences and resulting in suboptimal preference estimation. Second, current algorithms typically rely on deterministic rules to initiate conversations, causing unnecessary interactions when preferences are well-understood and missed opportunities when preferences are uncertain. To address these limitations, we propose three novel algorithms: CLiSK, CLiME, and CLiSK-ME. CLiSK introduces smoothed key term contexts to enhance exploration in preference learning, CLiME adaptively initiates conversations based on preference uncertainty, and CLiSK-ME integrates both techniques. We theoretically prove that all three algorithms achieve a tighter regret upper bound of O (√dTlogT) with respect to the time horizon T, improving upon existing methods. Additionally, we provide a matching lower bound Ω(√dT) for conversational bandits, demonstrating that our algorithms are nearly minimax optimal. Extensive evaluations on both synthetic and real-world datasets show that our approaches achieve at least a 14.6% improvement in cumulative regret.

In conversational recommender systems, interactively presenting queries and leveraging user feedback are crucial for efficiently estimating user preferences and improving recommendation quality. Selecting optimal queries in these systems is a significant challenge that has been extensively studied as a sequential decision problem. The expected value of information (EVOI), which computes the expected reward improvement, provides a principled criterion for query selection. However, it is computationally expensive and lacks theoretical performance guarantees. Conversely, conversational bandits offer provable regret upper bounds, but their query selection strategies yield only marginal regret improvements over non-conversational approaches. To address these limitations, we integrate EVOI within the conversational bandit framework by proposing a new conversational mechanism featuring two key techniques: (1) gradient-based EVOI, which replaces the complex Bayesian updates in conventional EVOI with efficient stochastic gradient descent, significantly reducing computational complexity and facilitating theoretical analysis; and (2) smoothed key term contexts, which enhance exploration by adding random perturbations to uncover more specific user preferences. Our approach applies to both Bayesian (Thompson Sampling) and frequentist (UCB) variants of conversational bandits. We introduce two new algorithms, ConTS-EVOI and ConUCB-EVOI, and rigorously prove that they achieve substantially tighter regret bounds, with both algorithms offering a √d improvement in their dependence on the time horizon T, where d is the dimension of the feature space. Extensive evaluations on synthetic and real-world datasets validate the effectiveness of our methods.

Large-scale quantum networks with thousands of nodes require topology-oblivious routing protocols to realize. Most existing quantum network routing protocols only consider the intra-domain scenario, where all nodes belong to a single party with complete topology knowledge. However, like the classical Internet, quantum Internet will likely be provided by multiple quantum Internet Service Providers (qISPs). In this paper, we consider the inter-domain scenario, where the network consists of multiple subnetworks owned by mutually untrusted parties without centralized control. Under this setting, previously proposed quantum entanglement routing policies, which rely on the network topology knowledge, are no longer applicable. We propose a Quantum Border Gateway Protocol (QBGP) for efficiently routing entanglement across qISP boundaries. To guarantee high-quality information transmission, we propose an algorithm named online top-K path selection. This algorithm utilizes the information gain introduced in this paper to adaptively decide on measurement parameters, allowing for the selection of high-fidelity paths and accurate fidelity estimates, while minimizing costs. Additionally, we implement a quantum network simulator and evaluate our protocol and algorithm. Our evaluation shows that QBGP effectively distributes entanglement across different qISPs, and our path selection algorithm increases the network performance by selecting high-fidelity paths with much lower resource consumption than other methods.

Reliable transmission of fragile quantum information requires one to efficiently select and utilize high-fidelity links among multiple noisy quantum links. However, the fidelity, a quality metric of quantum links, is unknown a priori. Uniformly estimating the fidelity of all links can be expensive, especially in networks with numerous links. To address this challenge, we formulate the link selection and fidelity estimation problem as a best arm identification problem and propose an algorithm named LinkSelFiE. The algorithm efficiently identifies the optimal link from a set of quantum links and provides an accurate fidelity estimate of that link with low quantum resource consumption. LinkSelFiE estimates link fidelity based on the feedback of a vanilla network benchmarking subroutine, and adaptively eliminates inferior links throughout the whole fidelity estimation process. This elimination leverages a novel confidence interval derived in this paper for the estimates from the subroutine, which theoretically guarantees that LinkSelFiE outputs the optimal link correctly with high confidence. We also establish a provable upper bound of cost complexity for LinkSelFiE. Moreover, we perform extensive simulations under various scenarios to corroborate that LinkSelFiE outperforms other existing methods in terms of both identifying the optimal link and reducing quantum resource consumption.

With diverse functionalities and advanced platform applications, Internet of Things (IoT) devices extensively interact with each other, and these interactions govern the legitimate device state transitions. At the same time, attackers can easily manipulate these devices, and it is difficult to detect covert device control. In this work, we propose the device interaction graph, which uses device interactions to profile normal device behavior. We also formalize two types of device anomalies, and present an anomaly detection system CausalIoT. It can automatically construct the graph and validate runtime device events. For any violation of interaction executions, CausalIoT further checks whether it can trigger unexpected interaction executions and tracks the affected devices.1 Compared with existing methods, CausalIoT achieves the highest detection accuracy for abnormal device state transitions (95.2% precision and 96.8% recall). Moreover, we are the first to detect unexpected interaction executions, and CausalIoT successfully reports 91.9% anomaly chains on real-world testbeds.

Internet of Things (IoT) services are gaining increasing popularity, and IoT devices are widely deployed at many smart homes. Among all the IoT communication protocols, Zigbee is a dominant one used by billions of devices and customers. However, the design of Zigbee has not been carefully evaluated and could be exploited by attackers. In this paper, we focus on Zigbee’s network rejoin procedure, which aims to allow devices to automatically recover their network status when they accidentally go offline. We develop an automated verification tool Verejoin to perform a systematic study on the rejoin procedure. Using this tool, we not only confirm a well-known design flaw, but also reveal two undiscovered design flaws. Moreover, we construct four proof-of-concept (PoC) attacks to exploit these design flaws. These vulnerabilities create new attack surfaces for attackers to manipulate Zigbee devices, and the damage of these vulnerabilities ranges from denial of service to device hijacking. We further design a Zigbee testing tool ZigHomer to confirm these vulnerabilities in real-world devices. Using ZigHomer, we conduct thorough evaluations of off-the-shelf Zigbee devices from leading IoT vendors, and the evaluation result shows the prevalence and severity of these vulnerabilities. Finally, we reported our findings to related parties, and they all acknowledged the significant security impact. We further collaborate with Zigbee Alliance to amend the Zigbee specification, and successfully addressed our reported vulnerabilities.

Safe system programming is often a crucial requirement due to its critical role in system software engineering. Conventional low-level programming languages such as C and assembly are efficient, but their inherent unsafe nature makes it undesirable for security-critical scenarios. Recently, Rust has become a promising alternative for safe system-level programming. While giving programmers fine-grained hardware control, its strong type system enforces many security properties including memory safety. However, Rust's security guarantee is not a silver bullet. Runtime crashes and memory-safety errors still harass Rust developers, causing damaging exploitable vulnerabilities, as reported by numerous studies.

Device drivers on Linux-powered embedded or IoT systems execute in kernel space thus must be fully trusted. Any fault in drivers may significantly impact the whole system. However, third-party embedded hardware manufacturers usually ship their proprietary device drivers with their embedded devices. These out-of-tree device drivers are generally of poor quality because of a lack of code audit. In this paper, we propose a new approach that helps third-party developers to improve the reliability and safety of device drivers without modifying the kernel: Rewriting device drivers in a memory-safe programming language called Rust. Rust's rigorous language model assists the device driver developers to detect many security issues at compile time. We designed a framework to help developers to quickly build device drivers in Rust. We also utilized Rust's security features to provide several useful infrastructures for developers so that they can easily handle kernel memory allocation and concurrency management, at the same time, some common bugs (e.g. use-after-free) can be alleviated. We demonstrate the generality of our framework by implementing a real-world device driver on Raspberry Pi 3, and our evaluation shows that device drivers generated by our framework have acceptable binary size for canonical embedded systems and the runtime overhead is negligible.