Search

The combination of the Bayesian game and learning has a rich history, with the idea of controlling a single agent in a system composed of multiple agents with unknown behaviors given a set of types, each specifying a possible behavior for the other agents. The idea is to plan an agent's own actions with respect to those types which it believes are most likely to maximize the payoff. However, the type beliefs are often learned from past actions and likely to be incorrect. With this perspective in mind, we consider an agent in a game with type predictions of other components, and investigate the impact of incorrect beliefs to the agent's payoff. In particular, we formally define a tradeoff between risk and opportunity by comparing the payoff obtained against the optimal payoff, which is represented by a gap caused by trusting or distrusting the learned beliefs. Our main results characterize the tradeoff by establishing upper and lower bounds on the Pareto front for both normal-form and stochastic Bayesian games, with numerical results provided., Comment: 26 pages, NeurIPS 2024

With the rapid development of electric vehicles (EVs) and vehicle-to-grid (V2G) technology, detecting malicious EV drivers is becoming increasingly important for the reliability and efficiency of smart grids. To address this challenge, machine learning (ML) algorithms are employed to predict user behavior and identify patterns of non-cooperation. However, the ML predictions are often untrusted, which can significantly degrade the performance of existing algorithms. In this paper, we propose a safety-enabled group testing scheme, \ouralg, which combines the efficiency of probabilistic group testing with ML predictions and the robustness of combinatorial group testing. We prove that \ouralg is $O(d)$-consistent and $O(d\log n)$-robust, striking a near-optimal trade-off. Experiments on synthetic data and case studies based on \textsc{ACN-Data}, a real-world EV charging dataset validate the efficacy of \ouralg for efficiently detecting malicious users in V2G systems. Our findings contribute to the growing field of algorithms with predictions and provide insights for incorporating distributional ML advice into algorithmic decision-making in energy and transportation-related systems.

In-context reinforcement learning (ICRL) is a frontier paradigm for solving reinforcement learning problems in the foundation model era. While ICRL capabilities have been demonstrated in transformers through task-specific training, the potential of Large Language Models (LLMs) out-of-the-box remains largely unexplored. Recent findings highlight that LLMs often face challenges when dealing with numerical contexts, and limited attention has been paid to evaluating their performance through preference feedback generated by the environment. This paper is the first to investigate LLMs as in-context decision-makers under the problem of Dueling Bandits (DB), a stateless preference-based reinforcement learning setting that extends the classic Multi-Armed Bandit (MAB) model by querying for preference feedback. We compare GPT-3.5 Turbo, GPT-4, GPT-4 Turbo, Llama 3.1, and o1-Preview against nine well-established DB algorithms. Our results reveal that our top-performing LLM, GPT-4 Turbo, has the zero-shot relative decision-making ability to achieve surprisingly low weak regret across all the DB environment instances by quickly including the best arm in duels. However, an optimality gap exists between LLMs and classic DB algorithms in terms of strong regret. LLMs struggle to converge and consistently exploit even when explicitly prompted to do so, and are sensitive to prompt variations. To bridge this gap, we propose an agentic flow framework: LLM with Enhanced Algorithmic Dueling (LEAD), which integrates off-the-shelf DB algorithms with LLM agents through fine-grained adaptive interplay. We show that LEAD has theoretical guarantees inherited from classic DB algorithms on both weak and strong regret. We validate its efficacy and robustness even with noisy and adversarial prompts. The design of our framework sheds light on how to enhance the trustworthiness of LLMs used for in-context decision-making.

Public models offer predictions to a variety of downstream tasks and have played a crucial role in various AI applications, showcasing their proficiency in accurate predictions. However, the exclusive emphasis on prediction accuracy may not align with the diverse end objectives of downstream agents. Recognizing the public model's predictions as a service, we advocate for integrating the objectives of downstream agents into the optimization process. Concretely, to address performance disparities and foster fairness among heterogeneous agents in training, we propose a novel Equitable Objective. This objective, coupled with a policy gradient algorithm, is crafted to train the public model to produce a more equitable/uniform performance distribution across downstream agents, each with their unique concerns. Both theoretical analysis and empirical case studies have proven the effectiveness of our method in advancing performance equity across diverse downstream agents utilizing the public model for their decision-making. Codes and datasets are released at https://github.com/Ren-Research/Socially-Equitable-Public-Models., Comment: Accepted by the ICML 2024

We tackle the challenge of learning to charge Electric Vehicles (EVs) with Out-of-Distribution (OOD) data. Traditional scheduling algorithms typically fail to balance near-optimal average performance with worst-case guarantees, particularly with OOD data. Model Predictive Control (MPC) is often too conservative and data-independent, whereas Reinforcement Learning (RL) tends to be overly aggressive and fully trusts the data, hindering their ability to consistently achieve the best-of-both-worlds. To bridge this gap, we introduce a novel OOD-aware scheduling algorithm, denoted OOD-Charging. This algorithm employs a dynamic "awareness radius", which updates in real-time based on the Temporal Difference (TD)-error that reflects the severity of OOD. The OOD-Charging algorithm allows for a more effective balance between consistency and robustness in EV charging schedules, thereby significantly enhancing adaptability and efficiency in real-world charging environments. Our results demonstrate that this approach improves the scheduling reward reliably under real OOD scenarios with remarkable shifts of EV charging behaviors caused by COVID-19 in the Caltech ACN-Data., Comment: 12 pages, 7 figures

This paper studies the problem of Anytime-Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected cost over random dynamics, but the cost in a specific episode can still be unsatisfactorily high. In contrast, the goal of A-CMDP is to optimize the expected reward while guaranteeing a bounded cost in each round of any episode against a policy prior. We propose a new algorithm, called Anytime-Competitive Reinforcement Learning (ACRL), which provably guarantees the anytime cost constraints. The regret analysis shows the policy asymptotically matches the optimal reward achievable under the anytime competitive constraints. Experiments on the application of carbon-intelligent computing verify the reward performance and cost constraint guarantee of ACRL., Comment: Accepted by NeurIPS 2023

We study the tradeoff between consistency and robustness in the context of a single-trajectory time-varying Markov Decision Process (MDP) with untrusted machine-learned advice. Our work departs from the typical approach of treating advice as coming from black-box sources by instead considering a setting where additional information about how the advice is generated is available. We prove a first-of-its-kind consistency and robustness tradeoff given Q-value advice under a general MDP model that includes both continuous and discrete state/action spaces. Our results highlight that utilizing Q-value advice enables dynamic pursuit of the better of machine-learned advice and a robust baseline, thus result in near-optimal performance guarantees, which provably improves what can be obtained solely with black-box advice., Comment: 32 pages, NeurIPS 2023

The wide deployment of distributed renewable energy sources and electric vehicles can help mitigate climate crisis. This necessitates new business models in the power sector to hedge against uncertainties while imposing a strong coupling between the connected power and transportation networks. To address these challenges, this paper first proposes an energy sharing mechanism considering AC power network constraints to encourage local energy exchange in the power system. Under the proposed mechanism, all prosumers play a generalized Nash game. We prove that the energy sharing equilibrium exists and is socially optimal. Furthermore, a hierarchical game is built to characterize the interactions both inside and between the power and transportation systems. Externally, the two systems are engaged in a generalized Nash game because traffic flows serve as electric demands by charging behaviors, and each driver pays the energy sharing price for charging. The hierarchical game is then converted into a mixed-integer linear program (MILP) with the help of optimality conditions and linearization techniques. Numerical experiments validate the theoretical results and show the mutual impact between the two systems., Comment: 15 pages, 17 figures

We study Model Predictive Control (MPC) and propose a general analysis pipeline to bound its dynamic regret. The pipeline first requires deriving a perturbation bound for a finite-time optimal control problem. Then, the perturbation bound is used to bound the per-step error of MPC, which leads to a bound on the dynamic regret. Thus, our pipeline reduces the study of MPC to the well-studied problem of perturbation analysis, enabling the derivation of regret bounds of MPC under a variety of settings. To demonstrate the power of our pipeline, we use it to generalize existing regret bounds on MPC in linear time-varying (LTV) systems to incorporate prediction errors on costs, dynamics, and disturbances. Further, our pipeline leads to regret bounds on MPC in systems with nonlinear dynamics and constraints.

Machine-learned black-box policies are ubiquitous for nonlinear control problems. Meanwhile, crude model information is often available for these problems from, e.g., linear approximations of nonlinear dynamics. We study the problem of equipping a black-box control policy with model-based advice for nonlinear control on a single trajectory. We first show a general negative result that a naive convex combination of a black-box policy and a linear model-based policy can lead to instability, even if the two policies are both stabilizing. We then propose an adaptive $\lambda$-confident policy, with a coefficient $\lambda$ indicating the confidence in a black-box policy, and prove its stability. With bounded nonlinearity, in addition, we show that the adaptive $\lambda$-confident policy achieves a bounded competitive ratio when a black-box policy is near-optimal. Finally, we propose an online learning approach to implement the adaptive $\lambda$-confident policy and verify its efficacy in case studies about the CartPole problem and a real-world electric vehicle (EV) charging problem with data bias due to COVID-19., Comment: 33 pages, 7 figures

We study the problem of phase optimization for electric-vehicle (EV) charging. We formulate our problem as a non-convex mixed-integer programming problem whose objective is to minimize the charging loss. Despite the hardness of directly solving this non-convex problem, we solve a relaxation of the original problem by proposing the PXA algorithm where "P", "X", and "A" stand for three variable matrices in the formed phase optimization problems. We show that under certain conditions, the solution is given by the PXA precisely converges to the global optimum. In addition, using the idea of model predictive control (MPC), we design the {PXA-MPC}, which is an online implementation of the PXA. Compared to other empirical phase balancing strategies, the PXA algorithm significantly improves the charging performance by maximizing energy delivery, minimizing charging price, and assisting future energy planning. The efficacy of our algorithm is demonstrated using data collected from a real-world adaptive EV charging network (ACN)., Comment: 8 pages, 6 figures, accepted by PSCC 2022

Energy storage is expected to play an increasingly important role in mitigating variations that come along with the growing penetration of renewable energy. In this paper, we study the optimal bidding of an energy storage unit in a semi-centralized market. The energy storage unit offers its available storage capacity and maximum charging/discharging rate to the operator; then the operator clears the real-time market by minimizing the total cost. The energy storage unit is paid/charged at locational marginal price (LMP). The problem casts down to a bilevel optimization problem with a mixed-integer lower-level. An improved surrogate-based method with the combined spatial-temporal entropy term is developed to solve this problem. Numerical examples demonstrate the scalability, efficiency, and accuracy of the proposed method., Comment: 5 pages, 5 figures

We study the problem of learning-augmented predictive linear quadratic control. Our goal is to design a controller that balances \textit{"consistency"}, which measures the competitive ratio when predictions are accurate, and \textit{"robustness"}, which bounds the competitive ratio when predictions are inaccurate. We propose a novel $\lambda$-confident policy and provide a competitive ratio upper bound that depends on a trust parameter $\lambda\in [0,1]$ set based on the confidence in the predictions and some prediction error $\varepsilon$. Motivated by online learning methods, we design a self-tuning policy that adaptively learns the trust parameter $\lambda$ with a competitive ratio that depends on $\varepsilon$ and the variation of system perturbations and predictions. We show that its competitive ratio is bounded from above by $ 1+{O(\varepsilon)}/({{\Theta(1)+\Theta(\varepsilon)}})+O(\mu_{\mathsf{Var}})$ where $\mu_\mathsf{Var}$ measures the variation of perturbations and predictions. It implies that when the variations of perturbations and predictions are small, by automatically adjusting the trust parameter online, the self-tuning scheme ensures a competitive ratio that does not scale up with the prediction error $\varepsilon$., Comment: 34 pages, 8 figures, ACM SIGMETRICS 2022

Recently, deep learning has been an area of intense research. However, as a kind of computing-intensive task, deep learning highly relies on the scale of GPU memory, which is usually prohibitive and scarce. Although some extensive works have been proposed for dynamic GPU memory management, they are hard to apply to systems with multiple dynamic workloads, such as in-database machine learning systems. In this paper, we demonstrated TENSILE, a method of managing GPU memory in tensor granularity to reduce the GPU memory peak, considering the multiple dynamic workloads. TENSILE tackled the cold-starting and across-iteration scheduling problem existing in previous works. We implemented TENSILE on a deep learning framework built by ourselves and evaluated its performance. The experiment results show that TENSILE can save more GPU memory with less extra overhead than prior works in single and multiple dynamic workloads scenarios.

Discovering the complete set of causal relations among a group of variables is a challenging unsupervised learning problem. Often, this challenge is compounded by the fact that there are latent or hidden confounders. When only observational data is available, the problem is ill-posed, i.e. the causal relationships are non-identifiable unless strong modeling assumptions are made. When interventions are available, we provide guarantees on identifiability and learnability under mild assumptions. We assume a linear structural equation model (SEM) with independent latent factors and directed acyclic graph (DAG) relationships among the observables. Since the latent variable inference is based on independent component analysis (ICA), we call this model SEM-ICA. We use the method of moments principle to establish model identifiability. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions. Thus, we provide a principled approach to tackling the joint problem of causal discovery and latent variable inference.

Aggregators have emerged as crucial tools for the coordination of distributed, controllable loads. To be used effectively, an aggregator must be able to communicate the available flexibility of the loads they control, as known as the aggregate flexibility to a system operator. However, most of existing aggregate flexibility measures often are slow-timescale estimations and much less attention has been paid to real-time coordination between an aggregator and an operator. In this paper, we consider solving an online optimization in a closed-loop system and present a design of real-time aggregate flexibility feedback, termed the maximum entropy feedback (MEF). In addition to deriving analytic properties of the MEF, combining learning and control, we show that it can be approximated using reinforcement learning and used as a penalty term in a novel control algorithm -- the penalized predictive control (PPC), which modifies vanilla model predictive control (MPC). The benefits of our scheme are (1). Efficient Communication. An operator running PPC does not need to know the exact states and constraints of the loads, but only the MEF. (2). Fast Computation. The PPC often has much less number of variables than an MPC formulation. (3). Lower Costs. We show that under certain regularity assumptions, the PPC is optimal. We illustrate the efficacy of the PPC using a dataset from an adaptive electric vehicle charging network and show that PPC outperforms classical MPC., Comment: 13 pages, 5 figures, extension of arXiv:2006.13814

We introduce and study a general version of the fractional online knapsack problem with multiple knapsacks, heterogeneous constraints on which items can be assigned to which knapsack, and rate-limiting constraints on the assignment of items to knapsacks. This problem generalizes variations of the knapsack problem and of the one-way trading problem that have previously been treated separately, and additionally finds application to the real-time control of electric vehicle (EV) charging. We introduce a new algorithm that achieves a competitive ratio within an additive factor of one of the best achievable competitive ratios for the general problem and matches or improves upon the best-known competitive ratio for special cases in the knapsack and one-way trading literatures. Moreover, our analysis provides a novel approach to online algorithm design based on an instance-dependent primal-dual analysis that connects the identification of worst-case instances to the design of algorithms. Finally, we illustrate the proposed algorithm via trace-based experiments of EV charging.

Aggregators have emerged as crucial tools for the coordination of distributed, controllable loads. However, to be used effectively, aggregators must be able to communicate the available flexibility of the loads they control to the system operator in a manner that is both (i) concise enough to be scalable to aggregators governing hundreds or even thousands of loads and (ii) informative enough to allow the system operator to send control signals to the aggregator that lead to optimization of system-level objectives, such as cost minimization, and do not violate private constraints of the loads, such as satisfying specific load demands. In this paper, we present the design of a real-time flexibility feedback signal based on maximization of entropy. The design provides a concise and informative signal that can be used by the system operator to perform online cost minimization and real-time capacity estimation, while provably satisfying the private constraints of the loads. In addition to deriving analytic properties of the design, we illustrate the effectiveness of the design using a dataset from an adaptive electric vehicle charging network., Comment: The Eleventh ACM International Conference on Future Energy Systems (e-Energy'20)

The mushrooming of distributed energy resources turns end-users from passive price-takers to active market participants. To manage those massive proactive end-users efficiently, virtual power plant (VPP) as an innovative concept emerges. It can provide some necessary information to help consumers improve their profits and trade with the electricity market on behalf of them. One important information that is desired by the consumers is the prediction of renewable outputs inside this VPP. Presently, most VPPs run in a centralized manner, which means the VPP predicts the outputs of all the renewable sources it manages and provides the predictions to every consumer who buys this information. We prove that by providing predictions, the social total surplus can be improved. However, when more consumers and renewables participate in the market, this centralized scheme needs extensive data communication and may jeopardize the privacy of individual stakeholders. In this paper, we propose a decentralized prediction provision algorithm in which consumers from each subregion only buy local predictions and exchange information with the VPP. Convergence is proved under a mild condition, and the demand gap between centralized and decentralized schemes is proved to have zero expectation and bounded variance. Illustrative examples show that the variance of this gap decreases with more consumers and higher uncertainty, and validate the proposed algorithm numerically., Comment: 13 pages, 9 figures

Intel SGX Guard eXtensions (SGX), a hardware-supported trusted execution environment (TEE), is designed to protect security-sensitive applications. However, since enclave applications are developed with memory unsafe languages such as C/C++, traditional memory corruption is not eliminated in SGX. Rust-SGX is the first toolkit providing enclave developers with a memory-language. However, Rust is considered a Systems language and has become the right choice for concurrent applications and web browsers. Many application domains such as Big Data, Machine Learning, Robotics, Computer Vision are more commonly developed in the python programming language. Therefore, Python application developers cannot benefit from secure enclaves like Intel SGX and rust-SGX. To fill this gap, we propose Python-SGX, which is a memory-safe SGX SDK providing enclave developers a memory-safe Python development environment. The key idea is to enable memory-safe Python language in SGX by solving the following key challenges: (1) defining a memory-safe Python interpreter (2)replacing unsafe elements of Python interpreter with safe ones,(3) achieving comparable performance to non-enclave Python applications, and (4) not introducing any unsafe new code or libraries into SGX. We propose to build Python-SGX with PyPy, a Python interpreter written by RPython, which is a subset of Python, and tame unsafe parts in PyPy by formal verification, security hardening, and memory safe language. We have implemented python-SGX and tested it with a series of benchmarks programs. Our evaluation results show that Python-SGX does not cause significant overhead.

The big data industry is facing new challenges as concerns about privacy leakage soar. One of the remedies to privacy breach incidents is to encapsulate computations over sensitive data within hardware-assisted Trusted Execution Environments (TEE). Such TEE-powered software is called secure enclaves. Secure enclaves hold various advantages against competing for privacy-preserving computation solutions. However, enclaves are much more challenging to build compared with ordinary software. The reason is that the development of TEE software must follow a restrictive programming model to make effective use of strong memory encryption and segregation enforced by hardware. These constraints transitively apply to all third-party dependencies of the software. If these dependencies do not officially support TEE hardware, TEE developers have to spend additional engineering effort in porting them. High development and maintenance cost is one of the major obstacles against adopting TEE-based privacy protection solutions in production. In this paper, we present our experience and achievements with regard to constructing and continuously maintaining a third-party library supply chain for TEE developers. In particular, we port a large collection of Rust third-party libraries into Intel SGX, one of the most mature trusted computing platforms. Our supply chain accepts upstream patches in a timely manner with SGX-specific security auditing. We have been able to maintain the SGX ports of 159 open-source Rust libraries with reasonable operational costs. Our work can effectively reduce the engineering cost of developing SGX enclaves for privacy-preserving data processing and exchange.

We consider a specific graph learning task: reconstructing a symmetric matrix that represents an underlying graph using linear measurements. We present a sparsity characterization for distributions of random graphs (that are allowed to contain high-degree nodes), based on which we study fundamental trade-offs between the number of measurements, the complexity of the graph class, and the probability of error. We first derive a necessary condition on the number of measurements. Then, by considering a three-stage recovery scheme, we give a sufficient condition for recovery. Furthermore, assuming the measurements are Gaussian IID, we prove upper and lower bounds on the (worst-case) sample complexity for both noisy and noiseless recovery. In the special cases of the uniform distribution on trees with n nodes and the Erdos-Renyi (n,p) class, the fundamental trade-offs are tight up to multiplicative factors with noiseless measurements. In addition, for practical applications, we design and implement a polynomial-time (in n) algorithm based on the three-stage recovery scheme. Experiments show that the heuristic algorithm outperforms basis pursuit on star graphs. We apply the heuristic algorithm to learn admittance matrices in electric grids. Simulations for several canonical graph classes and IEEE power system test cases demonstrate the effectiveness and robustness of the proposed algorithm for parameter reconstruction.

Motivated by a greedy approach for generating {\it{information stable}} processes, we prove a universal maximum likelihood (ML) upper bound on the capacities of discrete information stable channels, including the binary erasure channel (BEC), the binary symmetric channel (BSC) and the binary deletion channel (BDC). The bound is derived leveraging a system of equations obtained via the Karush-Kuhn-Tucker conditions. Intriguingly, for some memoryless channels, e.g., the BEC and BSC, the resulting upper bounds are tight and equal to their capacities. For the BDC, the universal upper bound is related to a function counting the number of possible ways that a length-$\lo$ binary subsequence can be obtained by deleting $n-m$ bits (with $n-m$ close to $nd$ and $d$ denotes the {\it{deletion probability}}) of a length-$n$ binary sequence. To get explicit upper bounds from the universal upper bound, it requires to compute a maximization of the matching functions over a Hamming cube containing all length-$n$ binary sequences. Calculating the maximization exactly is hard. Instead, we provide a combinatorial formula approximating it. Under certain assumptions, several approximations and an {\it{explicit}} upper bound for deletion probability $d\geq 1/2$ are derived., Comment: 14 pages, 3 figures