More Like this

1. Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedback

   https://doi.org/10.1145/3641512.3686369  

   Hou, I-Hong (October 2024, ACM)

   This paper studies multi-stage systems with end-to-end bandit feedback. In such systems, each job needs to go through multiple stages, each managed by a different agent, before generating an outcome. Each agent can only control its own action and learn the final outcome of the job. It has neither knowledge nor control on actions taken by agents in the next stage. The goal of this paper is to develop distributed online learning algorithms that achieve sublinear regret in adversarial environments. The setting of this paper significantly expands the traditional multi-armed bandit problem, which considers only one agent and one stage. In addition to the exploration-exploitation dilemma in the traditional multi-armed bandit problem, we show that the consideration of multiple stages introduces a third component, education, where an agent needs to choose its actions to facilitate the learning of agents in the next stage. To solve this newly introduced exploration-exploitation-education trilemma, we propose a simple distributed online learning algorithm, ϵ-EXP3. We theoretically prove that the ϵ-EXP3 algorithm is a no-regret policy that achieves sublinear regret. Simulation results show that the ϵ-EXP3 algorithm significantly outperforms existing no-regret online learning algorithms for the traditional multi-armed bandit problem. 

   more » « less
2. Maximum Profit Facility Location and Dynamic Resource Allocation for Instant Delivery Logistics

   https://doi.org/10.1177/03611981221082574  

   Rajesh_Chauhan, Darshan; Unnikrishnan, Avinash; Boyles, Stephen_D (March 2022, Transportation Research Record: Journal of the Transportation Research Board)

   Increasing e-commerce activity, competition for shorter delivery times, and innovations in transportation technologies have pushed the industry toward instant delivery logistics. This paper studies a facility location and online demand allocation problem applicable to a logistics company expanding to offer instant delivery service using unmanned aerial vehicles or drones. The problem is decomposed into two stages. During the planning stage, the facilities are located, and product and battery capacity are allocated. During the operational stage, customers place orders dynamically and real-time demand allocation decisions are made. The paper explores a multi-armed bandit framework for maximizing the cumulative reward realized by the logistics company subject to various capacity constraints and compares it with other strategies. The multi-armed bandit framework provides about 7% more rewards than the second-best strategy when tested on standard test instances. A case study based in Portland Metro Area showed that multi-armed bandits can outperform the second-best strategy by more than 20%. 

   more » « less
3. Dynamic Pricing for Autonomous Vehicle E-hailing Services Reliability and Performance Improvement

   https://doi.org/10.1109/COASE.2019.8843122  

   Wang, Qixing; Miao, Fei; Wu, Jie; Niu, Yuan; Wang, Chengliang; Lownes, Nicholas E. (September 2019, IEEE 15th International Conference on Automation Science and Engineering (CASE))

   As Autonomous Vehicles (AVs) become possible for E-hailing services operate, especially when telecom companies start deploying next-generation wireless networks (known as 5G), many new technologies may be applied in these vehicles. Dynamic-route-switching is one of these technologies, which could help vehicles find the best possible route based on real-time traffic information. However, allowing all AVs to choose their own optimal routes is not the best solution for a complex city network, since each vehicle ignores its negative effect on the road system due to the additional congestion it creates. As a result, with this system, some of the links may become over-congested, causing the whole road network system performance to degrade. Meanwhile, the travel time reliability, especially during the peak hours, is an essential factor to improve the customers' ride experience. Unfortunately, these two issues have received relatively less attention. In this paper, we design a link-based dynamic pricing model to improve the road network system and travel time reliability at the same time. In this approach, we assume that all links are eligible with the dynamic pricing, and AVs will be perfect informed with update traffic condition and follow the dynamic road pricing. A heuristic approach is developed to address this computationally difficult problem. The output includes link-based surcharge, new travel demand and traffic condition which would improve the system performance close to the System Optimal (SO) solution and maintain the travel time reliability. Finally, we evaluate the effectiveness and efficiency of the proposed model to the well-known test Sioux Falls network. 

   more » « less
4. Multi-Armed Bandits for Human-Machine Decision Making

   https://doi.org/10.1109/ICASSP.2018.8461843  

   Reverdy, Paul; Srivastava, Vaibhav (April 2018, 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   Building an integrated human-machine decision-making system requires developing effective interfaces between the human and the machine. We develop such an interface by studying the multi-armed bandit problem, a simple sequential decision-making paradigm that can model a variety of tasks. We construct Bayesian algorithms for the multi-armed ban- dit problem, prove conditions under which these algorithms achieve good performance, and empirically show that, with appropriate priors, these algorithms effectively model human choice behavior; the priors then form a principled interface from human to machine. We take a signal processing perspective on the prior estimation problem and develop methods to estimate the priors given human choice data. 

   more » « less
5. Job Dispatching Policies for Queueing Systems with Unknown Service Rates

   https://doi.org/10.1145/3466772.3467047  

   Choudhury, Tuhinangshu; Joshi, Gauri; Wang, Weina; Shakkottai, Sanjay (July 2021, ACM MobiHoc: International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks)

   null (Ed.)

   In multi-server queueing systems where there is no central queue holding all incoming jobs, job dispatching policies are used to assign incoming jobs to the queue at one of the servers. Classic job dispatching policies such as join-the-shortest-queue and shortest expected delay assume that the service rates and queue lengths of the servers are known to the dispatcher. In this work, we tackle the problem of job dispatching without the knowledge of service rates and queue lengths, where the dispatcher can only obtain noisy estimates of the service rates by observing job departures. This problem presents a novel exploration-exploitation trade-off between sending jobs to all the servers to estimate their service rates, and exploiting the currently known fastest servers to minimize the expected queueing delay. We propose a bandit-based exploration policy that learns the service rates from observed job departures. Unlike the standard multi-armed bandit problem where only one out of a finite set of actions is optimal, here the optimal policy requires identifying the optimal fraction of incoming jobs to be sent to each server. We present a regret analysis and simulations to demonstrate the effectiveness of the proposed bandit-based exploration policy. 

   more » « less