Mixed Integer Linear Programming (MILP) is essential for modeling complex decision-making problems but faces challenges in computational tractability and interpretability. Current deep learning approaches for MILP focus on specific problem classes and do not generalize to unseen classes. To address this shortcoming, we take a foundation model training approach, where we train a single deep learning model on a diverse set of MILP problems to generalize across problem classes. As existing datasets for MILP lack diversity and volume, we introduce MILP-Evolve, a novel LLM-based evolutionary framework that is capable of generating a large set of diverse MILP classes with an unlimited amount of instances. We study our methodology on three key learning tasks that capture diverse aspects of MILP: (1) integrality gap prediction, (2) learning to branch, and (3) a new task of aligning MILP instances with natural language descriptions. Our empirical results show that models trained on the data generated by MILP-Evolve achieve significant improvements on unseen problems, including MIPLIB benchmarks. Our work highlights the potential of moving towards a foundation model approach for MILP that can generalize to a broad range of MILP problem classes. Our code and data are publicly available at https://github.com/microsoft/OptiGuide.

Our analysis of a large public cloud ML training service shows that resources remain unused likely because users statically (over-)allocate resources for their jobs given a desire for predictable performance, and state-of-the-art schedulers do not exploit idle resources lest they slow down some jobs excessively. We consider if an anticipatory scheduler, which schedules based on predictions of future job arrivals and durations, can improve over the state-of-the-art. We find that realizing gains from anticipation requires dealing effectively with prediction errors, and even the best predictors have errors that do not conform to simple models (such as bounded or i.i.d. error). We devise a novel anticipatory scheduler called SIA that is robust to such errors. On real workloads, SIA reduces job latency by an average of 2.83× over the current production scheduler, while reducing the likelihood of job slowdowns by orders of magnitude relative to schedulers that naïvely share resources.

Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem – allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods.

Oversubscription is an essential cost management strategy for cloud database providers, and its importance is magnified by the emerging paradigm of serverless databases. In contrast to general purpose techniques used for oversubscription in hypervisors, operating systems and cluster managers, we develop techniques that leverage our understanding of how DBMSs use resources and how resource allocations impact database performance. Our techniques are designed to flexibly redistribute resources across database tenants at the node and cluster levels with low overhead. We have implemented our techniques in a commercial cloud database service: Azure SQL Database. Experiments using microbenchmarks, industry-standard benchmarks and real-world resource usage traces show that using our approach, it is possible to tightly control the impact on database performance even with a relatively high degree of oversubscription.

Cloud computing customers often submit repeating jobs and computation pipelines on approximately regular schedules, with arrival and running times that exhibit variance. This pattern, typical of training tasks in machine learning, allows customers to partially predict future job requirements. We develop a model of cloud computing platforms that receive statements of work (SoWs) in an online fashion. The SoWs describe future jobs whose arrival times and durations are probabilistic, and whose utility to the submitting agents declines with completion time. The arrival and duration distributions, as well as the utility functions, are considered private customer information and are reported by strategic agents to a scheduler that is optimizing for social welfare.

Large food-service companies typically support a wide range of operations (catering, vending machines, repairs), each with different operational characteristics (manpower, vehicles, tools, timing constraints, etc.). While the advances in Internet-based technologies facilitate the adoption of automated scheduling systems, the complexity and heterogeneity of the different operations hinders the design of comprehensive optimization solutions. Indeed, our collaboration with Compass Group, one of the largest food-service companies in the world, reveals that many of its workforce assignments are done manually due to the lack of scheduling solutions that can accommodate the complexity of operational constraints. Further, the diversity in the nature of operations prevents collaboration and sharing of resources among various services such as catering and beverage distribution, leading to an inflated fleet size.

In this paper, we describe Multi-Itinerary Optimization (MIO) - a novel Bing maps service that automates the process of building itineraries for multiple agents while optimizing their routes to save travel time or distance. MIO can be used by organizations with a fleet of vehicles and drivers, mobile salesforce, or a team of personnel in the field in order to maximize workforce efficiency. MIO accounts for service time windows, duration, and priority, as well as traffic conditions between locations, resulting in challenging algorithmic problems at multiple levels (e.g., calculating travel-time distance matrices at scale, scheduling services for multiple agents).

To keep up with the continuous growth in demand, cloud providers spend millions of dollars augmenting the capacity of their wide-area backbones and devote significant effort to efficiently utilizing WAN capacity. A key challenge is striking a good balance between network utilization and availability, as these are inherently at odds; a highly utilized network might not be able to withstand unexpected traffic shifts resulting from link/node failures. We advocate a novel approach to this challenge that draws inspiration from financial risk theory: leverage empirical data to generate a probabilistic model of network failures and maximize bandwidth allocation to network users subject to an operator-specified availability target. Our approach enables network operators to strike the utilization-availability balance that best suits their goals and operational reality. We present TEAVAR (Traffic Engineering Applying Value at Risk), a system that realizes this risk management approach to traffic engineering (TE). We compare TEAVAR to state-of-the-art TE solutions through extensive simulations across many network topologies, failure scenarios, and traffic patterns, including benchmarks extrapolated from Microsoft's WAN. Our results show that with TEAVAR, operators can support up to twice as much throughput as state-of-the-art TE schemes, at the same level of availability.

We consider a common setting where storage is disaggregated from the compute in data-parallel systems. Colocating caching tiers with the compute machines can reduce load on the interconnect but doing so leads to new resource management challenges. We design a system Netco, which prefetches data into the cache (based on workload predictability), and appropriately divides the cache space and network bandwidth between the prefetches and serving ongoing jobs. Netco makes various decisions (what content to cache, when to cache and how to apportion bandwidth) to support end-to-end optimization goals such as maximizing the number of jobs that meet their service-level objectives (e.g., deadlines). Our implementation of these ideas is available within the open-source Apache HDFS project. Experiments on a public cloud, with production-trace inspired workloads, show that Netco uses up to 5x less remote I/O compared to existing techniques and increases the number of jobs that meet their deadlines up to 80%.

Multi-tenant distributed systems composed of small services, such as Service-oriented Architectures (SOAs) and Micro-services, raise new challenges in attaining high performance and efficient resource utilization. In these systems, a request execution spans tens to thousands of processes, and the execution paths and resource demands on different services are generally not known when a request first enters the system. In this paper, we highlight the fundamental challenges of regulating load and scheduling in SOAs while meeting end-to-end performance objectives on metrics of concern to both tenants and operators. We design Wisp, a framework for building SOAs that transparently adapts rate limiters and request schedulers system-wide according to operator policies to satisfy end-to-end goals while responding to changing system conditions. In evaluations against production as well as synthetic workloads, Wisp successfully enforces a range of end-to-end performance objectives, such as reducing average latencies, meeting deadlines, providing fairness and isolation, and avoiding system overload.

Distributed actor systems are widely used for developing interactive scalable cloud services, such as social networks and on-line games. By modeling an application as a dynamic set of lightweight communicating "actors", developers can easily build complex distributed applications, while the underlying runtime system deals with low-level complexities of a distributed environment.

Resource management problems in systems and networking often manifest as difficult online decision making tasks where appropriate solutions depend on understanding the workload and environment. Inspired by recent advances in deep reinforcement learning for AI problems, we consider building systems that learn to manage resources directly from experience. We present DeepRM, an example solution that translates the problem of packing tasks with multiple resource demands into a learning problem. Our initial results show that DeepRM performs comparably to state-of-the-art heuristics, adapts to different conditions, converges quickly, and learns strategies that are sensible in hindsight.

Neither traffic engineering nor fixed prices (e.g., \$/GB) alone fully address the challenges of highly utilized inter-datacenter WANs. The former offers more service to users who overstate their demands and poor service overall. The latter offers no service guarantees to customers, and providers have no lever to steer customer demand to lightly loaded paths/times. To address these issues, we design and evaluate Pretium -- a framework that combines dynamic pricing with traffic engineering for inter-datacenter bandwidth. In Pretium, users specify their required rates or transfer sizes with deadlines, and a price module generates a price quote for different guarantees (promises) on these requests. The price quote is generated using internal prices (which can vary over time and links) which are maintained and periodically updated by Pretium based on history. A supplementary schedule adjustment module gears the agreed-upon network transfers towards an efficient operating point by optimizing time-varying operation costs. Experiments using traces from a large production WAN show that Pretium improves total system efficiency (value of routed transfers minus operation costs) by more than 3.5X relative to current usage-based pricing schemes, while increasing the provider profits by 2X.

To reduce the impact of network congestion on big data jobs, cluster management frameworks use various heuristics to schedule compute tasks and/or network flows. Most of these schedulers consider the job input data fixed and greedily schedule the tasks and flows that are ready to run. However, a large fraction of production jobs are recurring with predictable characteristics, which allows us to plan ahead for them. Coordinating the placement of data and tasks of these jobs allows for significantly improving their network locality and freeing up bandwidth, which can be used by other jobs running on the cluster. With this intuition, we develop Corral, a scheduling framework that uses characteristics of future workloads to determine an offline schedule which (i) jointly places data and compute to achieve better data locality, and (ii) isolates jobs both spatially (by scheduling them in different parts of the cluster) and temporally, improving their performance. We implement Corral on Apache Yarn, and evaluate it on a 210 machine cluster using production workloads. Compared to Yarn's capacity scheduler, Corral reduces the makespan of these workloads up to 33% and the median completion time up to 56%, with 20-90% reduction in data transferred across racks.

We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cloud scheduling, but there are strong lower bounds even for the algorithmic problem without incentive constraints. However, these lower bounds can be circumvented under the natural assumption of deadline slackness, i.e., that there is a guaranteed lower bound s > 1 on the ratio between a job's size and the time window in which it can be executed. In this paper, we construct a truthful scheduling mechanism with a constant competitive ratio, given slackness s > 1. Furthermore, we show that if s is large enough then we can construct a mechanism that also satisfies a commitment property: it can be determined whether or not a job will finish, and the requisite payment if so, well in advance of each job's deadline. This is notable because, in practice, users with strict deadlines may find it unacceptable to discover only very close to their deadline that their job has been rejected.

Modern software applications and services operate nowadays on top of large clusters and datacenters. To reduce the underlying infrastructure cost and increase utilization, different services share the same physical resources (e.g., CPU, bandwidth, I/O, memory). Consequently, the cluster provider often has to decide in real-time how to allocate resources in overbooked systems, taking into account the different characteristics and requirements of users. In this paper, we consider an important problem within this space -- how to share memory between users, whose memory access patterns are unknown in advance. We assume that the overall performance (or cost) of each user is a non-linear function of the total number of misses over a given period of time. We develop an online caching algorithm for arbitrary cost functions. We further provide theoretical guarantees for convex functions (which capture plausible practical scenarios). In particular, our algorithm is αα kα-competitive, where k is the memory (cache) size, and α is a constant which depends on the curvature of the cost functions. We also obtain a bi-criteria result which trades-off the performance and the memory size. Finally, we give a lower bound on the performance of any online deterministic algorithm which nearly matches the upper bound of our algorithm.

Relational database-as-a-service (DaaS) providers need to rely on multi-tenancy and resource sharing among tenants, since statically reserving resources for a tenant is not cost effective. A major consequence of resource sharing is that the performance of one tenant can be adversely affected by resource demands of other co-located tenants. One such resource that is essential for good performance of a tenant's workload is buffer pool memory. In this paper, we study the problem of how to effectively share buffer pool memory in multi-tenant relational DaaS. We first develop an SLA framework that defines and enforces accountability of the service provider to the tenant even when buffer pool memory is not statically reserved on behalf of the tenant. Next, we present a novel buffer pool page replacement algorithm (MT-LRU) that builds upon theoretical concepts from weighted online caching, and is designed for multi-tenant scenarios involving SLAs and overbooking. MT-LRU generalizes the LRU-K algorithm which is commonly used in relational database systems. We have prototyped our techniques inside a commercial DaaS engine and extensive experiments demonstrate the effectiveness of our solution.

Datacenter WAN traffic consists of high priority transfers that have to be carried as soon as they arrive alongside large transfers with pre-assigned deadlines on their completion (ranging from minutes to hours). The ability to offer guarantees to large transfers is crucial for business needs and impacts overall cost-of-business. State-of-the-art traffic engineering solutions only consider the current time epoch and hence cannot provide pre-facto promises for long-lived transfers. We present Tempus, an online traffic engineering scheme that exploits information on transfer size and deadlines to appropriately pack long-running transfers across network paths and time, thereby leaving enough capacity slack for future high-priority requests. Tempus builds on a tailored approximate solution to a mixed packing-covering linear program, which is parallelizable and scales well in both running time and memory usage. Consequently, Tempus is able to quickly and effectively update its solution when new transfers arrive or unexpected changes happen. These updates involve only small edits to existing transfers. Therefore, as experiments on traces from a large production WAN show, Tempus can offer and keep promises to long-lived transfers well in advance of their actual deadline; the promise on minimal transfer size is comparable with an offline optimal solution and outperforms state-of-the-art solutions by 2-3X.

This paper presents a novel algorithm for scheduling big data jobs on large compute clusters. In our model, each job is represented by a DAG consisting of several stages linked by precedence constraints. The resource allocation per stage is malleable, in the sense that the processing time of a stage depends on the resources allocated to it (the dependency can be arbitrary in general).The goal of the scheduler is to maximize the total value of completed jobs, where the value for each job depends on its completion time. We design an algorithm for the problem which guarantees an expected constant approximation factor when the cluster capacity is sufficiently high. To the best of our knowledge, this is the first constant-factor approximation algorithm for the problem. The algorithm is based on formulating the problem as a linear program and then rounding an optimal (fractional) solution into a feasible (integral) schedule using randomized rounding.

We found that interactive services at Bing have highly variable datacenter-side processing latencies because their processing consists of many sequential stages, parallelization across 10s-1000s of servers and aggregation of responses across the network. To improve the tail latency of such services, we use a few building blocks: reissuing laggards elsewhere in the cluster, new policies to return incomplete results and speeding up laggards by giving them more resources. Combining these building blocks to reduce the overall latency is non-trivial because for the same amount of resource (e.g., number of reissues), different stages improve their latency by different amounts. We present Kwiken, a framework that takes an end-to-end view of latency improvements and costs. It decomposes the problem of minimizing latency over a general processing DAG into a manageable optimization over individual stages. Through simulations with production traces, we show sizable gains; the 99th percentile of latency improves by over 50% when just 0.1% of the responses are allowed to have partial results and by over 40% for 25% of the services when just 5% extra resources are used for reissues.

We consider mechanisms for online deadline-aware scheduling in large computing clusters. Batch jobs that run on such clusters often require guarantees on their completion time (i.e., deadlines). However, most existing scheduling systems implement fair-share resource allocation between users, an approach that ignores heterogeneity in job requirements and may cause deadlines to be missed.

Datacenter networks have been designed to tolerate failures of network equipment and provide sufficient bandwidth. In practice, however, failures and maintenance of networking and power equipment often make tens to thousands of servers unavailable, and network congestion can increase service latency. Unfortunately, there exists an inherent tradeoff between achieving high fault tolerance and reducing bandwidth usage in network core; spreading servers across fault domains improves fault tolerance, but requires additional bandwidth, while deploying servers together reduces bandwidth usage, but also decreases fault tolerance. We present a detailed analysis of a large-scale Web application and its communication patterns. Based on that, we propose and evaluate a novel optimization framework that achieves both high fault tolerance and significantly reduces bandwidth usage in the network core by exploiting the skewness in the observed communication patterns.

We consider a market-based resource allocation model for batch jobs in cloud computing clusters. In our model, we incorporate the importance of the due date of a job rather than the number of servers allocated to it at any given time. Each batch job is characterized by the work volume of total computing units (e.g., CPU hours) along with a bound on maximum degree of parallelism. Users specify, along with these job characteristics, their desired due date and a value for finishing the job by its deadline. Given this specification, the primary goal is to determine the scheduling} of cloud computing instances under capacity constraints in order to maximize the social welfare (i.e., sum of values gained by allocated users). Our main result is a new ( C/(C-k) ⋅ s/(s-1))-approximation algorithm for this objective, where C denotes cloud capacity, k is the maximal bound on parallelized execution (in practical settings, k l C) and s is the slackness on the job completion time i.e., the minimal ratio between a specified deadline and the earliest finish time of a job. Our algorithm is based on utilizing dual fitting arguments over a strengthened linear program to the problem.

We consider a dynamic spectrum access system in which Secondary Users (SUs) choose to either acquire dedicated spectrum or to use spectrum-holes (white spaces) which belong to Primary Users (PUs). The trade-off incorporated in this decision is between immediate yet costly transmission and free but delayed transmission (a consequence of both the possible appearance of PUs and sharing the spectrum holes with multiple SUs). We first consider a system with a single PU band, in which the SU decisions are fixed. Employing queueing-theoretic methods, we obtain explicit expressions for the expected delays associated with using the PU band. Based on that, we then consider self-interested SUs and study the interaction between them as a non-cooperative game. We prove the existence and uniqueness of a symmetric Nash equilibrium, and characterize the equilibrium behavior explicitly. Using our equilibrium results, we show how to maximize revenue from renting dedicated bands to SUs and briefly discuss the extension of our model to multiple PUs. Finally, since spectrum sensing can be resource-consuming, we characterize the gains provided by this capability.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit “water-filling” solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst-case performance guarantees in setups with arbitrarily varying channel conditions. We address both a “discrete” case, where the transmitter can transmit only at a fixed power level, and a “continuous” case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm and show that our proposed algorithms are optimal.

We consider scheduling over a wireless system, where the channel state information is not available a priori to the scheduler, but can be inferred from the past. Specifically, the wireless system is modeled as a network of parallel queues. We assume that the channel state of each queue evolves stochastically as an ON/OFF Markov chain. The scheduler, which is aware of the queue lengths but is oblivious of the channel states, has to choose one queue at a time for transmission. The scheduler has no information regarding the current channel states, but can estimate them by using the acknowledgment history. We first characterize the capacity region of the system using tools from Markov Decision Processes (MDP) theory. Specifically, we prove that the capacity region boundary is the uniform limit of a sequence of Linear Programming (LP) solutions. Next, we combine the LP solution with a queue length based scheduling mechanism that operates over long `frames,' to obtain a throughput optimal policy for the system. By incorporating results from MDP theory within the Lyapunov-stability framework, we show that our frame-based policy stabilizes the system for all arrival rates that lie in the interior of the capacity region.

We consider a dynamic spectrum access system in which Secondary Users (SUs) choose to either acquire dedicated spectrum or to use spectrum-holes (white spaces) which belong to Primary Users (PUs). The tradeoff incorporated in this decision is between immediate yet costly transmission and free but delayed transmission (a consequence of both the possible appearance of PUs and sharing the spectrum holes with multiple SUs). We first consider a system with a single PU band, in which the SU decisions are fixed. Employing queueing-theoretic methods, we obtain explicit expressions for the expected delays associated with using the PU band. Based on that, we then consider self-interested SUs and study the interaction between them as a noncooperative game. We prove the existence and uniqueness of a symmetric Nash equilibrium, and characterize the equilibrium behavior explicitly. Using our equilibrium results, we show how to maximize revenue from renting dedicated bands to SUs. Finally, we extend the scope to a scenario with multiple PUs, show that the band-pricing analysis can be applied to some special cases, and provide numerical examples.

We consider the power control problem in a time-slotted wireless channel, shared by a finite number of mobiles that transmit to a common base station. The channel between each mobile and the base station is time varying, and the system objective is to maximize the overall data throughput. It is assumed that each transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, by considering a realistic scenario where the channel quality of each mobile changes arbitrarily from one transmission to the other. Assuming first that each mobile is aware of the channel quality of all other mobiles, we propose an online power-allocation algorithm, and prove its optimality under mild assumptions. We then indicate how to implement the algorithm when only local state information is available, requiring minimal communication overhead. Notably, the competitive ratio of our algorithm (nearly) matches the one we previously obtained for the (much simpler) single-transmitter case [BLMNO09], albeit requiring significantly different algorithmic solutions.

We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically.

In transportation network research, the main approach for predicting traffic distribution due to noncooperative vehicle choices has been through fluid type models. The basic model considers a continuum of infinitesimal "non-atomic" vehicles, each seeking the shortest path to its destination. The resulting equilibrium turns out to be much simpler to characterize in comparison to the finite-vehicle case, yet provides a good approximation to the latter. A less familiar fluid-type model uses a continuum limit for the network topology. The limit network is a continuum plane which inherits its cost structure from the original network, and the corresponding equilibrium is identified as the continuum traffic equilibrium. This paper considers a similar equilibrium notion in a framework of a load balancing problem involving two processors, each requiring non-negligible workload (or "flow") to be handled by network resources. Besides a congestion cost at each resource (which is identical to both processors), each resource induces a processor-dependent connection cost, which is a function of its geographic location. The processors autonomously route their flow onto the different resources, with the objective of minimizing (non-cooperatively) their total cost. Assuming that the number of resources is relatively large, we apply the continuum approximation within a line (or bus) topology and study the Nash equilibria of the processor interaction. This approximation enables us to explicitly characterize the equilibrium in several cases and to obtain insights on its structure, including tight bounds on the efficiency loss due to noncooperation.

We consider decentralized medium-access control in which many pairwise interactions occur between randomly selected users that belong to a large population. In each local interaction, the users involved compete over an access opportunity. A given user has a fixed number of access attempts and a fixed budget for buying different priority levels. In each time-slot, the access is attributed to the user with the largest priority level. We analyze this problem under both cooperative as well as competitive frameworks. We show that unlike many standard team problems, optimal pure policies do not exist in the team framework, but both an optimal solution as well as equilibria exist within the class of mixed policies. We establish structural properties as well as explicit characterization of these: We show that the optimal policy requires only three priority levels, whereas the noncooperative game possesses a unique symmetric equilibrium point that uses at most two priority levels. Our analysis is applied to power control over wireless capture channels, where the budget constraint corresponds to the battery lifetime.

A major problem in wireless networks is coping with limited resources, such as bandwidth and energy. These issues become a major algorithmic challenge in view of the dynamic nature of the wireless domain. We consider in this paper the single-transmitter power assignment problem under time-varying channels, with the objective of maximizing the data throughput. It is assumed that the transmitter has a limited power budget, to be sequentially divided during the lifetime of the battery. We deviate from the classic work in this area, which leads to explicit "water-filling" solutions, by considering a realistic scenario where the channel state quality changes arbitrarily from one transmission to the other. The problem is accordingly tackled within the framework of competitive analysis, which allows for worst case performance guarantees in setups with arbitrarily varying channel conditions. We address both a "discrete" case, where the transmitter can transmit only at a fixed power level, and a "continuous" case, where the transmitter can choose any power level out of a bounded interval. For both cases, we propose online power-allocation algorithms with proven worst-case performance bounds. In addition, we establish lower bounds on the worst-case performance of any online algorithm, and show that our proposed algorithms are optimal.

We study a dynamic random access game with a finite number of opportunities for transmission and with energy constraints. We provide sufficient conditions for feasible strategies and for existence of Nash-Pareto solutions and show that finding Nash-Pareto policies of the dynamic random access game is equivalent to partitioning the set of time slot opportunities with constraints into a set of terminals. We further derive upper bounds for pure Nash-Pareto policies, and extend the study to non-integer energy constraints and unknown termination time, where Time Division Multiplexing policies can be suboptimal. We show that the dynamic random access game has several strong equilibria (resilient to coalition of any size), and we compute them explicitly. We introduce the (strong) price of anarchy concept to measure the gap between the payoff under strong equilibria and the social optimum.

We consider a time-slotted multipacket reception channel, shared by a finite number of mobile users who transmit to a common base station. Each user is allocated a fixed data rate, which may be imposed by the base station or self-determined. For sustaining the required rate over time, each user may adjust a single parameter which determines the individual transmission probability in a given slot. An equilibrium point is attained when the assigned data rates are met with equality. This paper analyzes the equilibrium points which result in this system, with a focus on power efficiency of the solution. While multiple equilibrium points exist in general, we establish that one of these equilibria is best for all users, in the sense that the transmission probability (hence the power investment) of each user is minimal. Further to the existence of worse equilibrium points, we point to the possibility of a partial- equilibrium with starvation, where stronger users (in terms of received power) satisfy their data rates, while preventing weaker ones from obtaining their respective rates. To avoid these sub- optimal working points, we suggest a distributed mechanism that converges to the best equilibrium point. Further analysis is provided for a specific channel model which involves perfect capture.

We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Users are self-optimizing, and each wishes to minimize its average transmission rate (or power investment), subject to minimum- throughput demand. The channel quality between each user and the base station is time-varying, and partially observed by the user in the form of channel state information (CSI) signals. We assume that each user can transmit at a fixed power level and that its transmission decision at each time slot is stationary in the sense that it can depend only on the current CSI. We are interested in properties of the Nash equilibrium of the resulting game between users. We define the feasible region of user's throughput demands, and show that when the demands are within this region, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of invested power) for all users. We further provide some lower bounds on the channel capacity that can be obtained, both in the symmetric and non-symmetric case. Finally, we show that a simple greedy mechanism converges to the best equilibrium point without requiring any coordination between the users.

We consider a wireless collision channel, shared by a finite number of mobile users who transmit to a common base station using a random access protocol. Mobiles are self-optimizing, and wish to minimize their individual average power investment subject to minimum-throughput demand. The channel state between each mobile and the base station is stochastically time-varying and is observed by the mobile prior to transmission. Given the current channel state, a mobile may decide whether to transmit or not, and to determine the transmission power in case of transmission. In this paper, we investigate the properties of the Nash equilibrium of the resulting game in multiuser networks.

We consider a wireless collision channel, shared by a finite number of users who transmit to a common base station. Each user wishes to minimize its average transmission rate (or power investment), subject to minimum throughput demand. The channel quality between each user and the base station is randomly time-varying, and partially observed by the user through Channel State Information (CSI) signals. Assuming that all users employ stationary, CSI-dependent transmission policies, we investigate the properties of the Nash equilibrium of the resulting game between users. We characterize the feasible region of user's throughput demands, and provide lower bounds on the channel capacity that hold both for symmetric and non-symmetric users. Our equilibrium analysis reveals that, when the throughput demands are feasible, there exist exactly two Nash equilibrium points, with one strictly better than the other (in terms of power investment) for each user. We further demonstrate that the performance gap between the two equilibria may be arbitrarily large. This motivates the need for distributed mechanisms that lead to the better equilibrium. To that end, we suggest a simple greedy (best-response) mechanism, and prove convergence to the better equilibrium. Some important stability properties of this mechanism in face of changing user population are derived as well.

We consider a graph theoretic approach for automatic construction of options in a dynamic environment. A map of the environment is generated on-line by the learning agent, representing the topological structure of the state transitions. A clustering algorithm is then used to partition the state space to different regions. Policies for reaching the different parts of the space are separately learned and added to the model in a form of options (macro-actions). The options are used for accelerating the Q-Learning algorithm. We extend the basic algorithm and consider building a map that includes preliminary indication of the location of "interesting" regions of the state space, where the value gradient is significant and additional exploration might be beneficial. Experiments indicate significant speedups, especially in the initial learning phase.