Learning & Optimization
Description
My recent research interests are in Reinforcement Learning and Bayesian Optimization. I am interested in the application of RL and BO for optimal stopping problems, control of queues and for dynamic pricing of commodities (with and without inventory effects).
Papers
U.Prakash, A. Chollera,K. Khatwani, K.J. Prabuchandran and T. Bodas “Practical First-Order Bayesian Optimization Algorithms,” 11th ACM IKDD CODS and 29th COMAD (CODS-COMAD) 2024 Bangalore, India. (pdf)
K.Jain, K.J. Prabuchandran and T. Bodas “Bayesian Optimization for Function Compositions with Applications to Dynamic Pricing,” Learning and Intelligent Optimization Conference (LION 17), NICE, France. (pdf)
K.J. Prabuchandran, T. Bodas and T. Theja “Reinforcement Learning algorithms for regret minimization in structured Markov Decision Processes,” extended abstract at AAMAS 2016, Singapore. (pdf)
US Patent US10176443B2: "Method and system for dispatching of vehicles in a public transportation network," with T. Thulabandhula and PK Jayachandran.
US Patent application 15232205: "Method and system for patient intake in healthcare network," with T. Thulabandhula and PK Jayachandran.
Load Balancing
Description
Imagine shopping at DMart. When you are done, you have to join a queue for payment. Which queue should you join? Welcome to load balancing! The shortest one, you would suppose (JSQ). But should you not factor in the basket size of your fellow shoppers? Should you not join the queue with the shortest work ahead (JSW)? But then there are so so so many payment counters! You cannot possibly estimate the workload at all these queues. What do you do then? What we inadvertently do is to randomly sample a few queues (say d) and then join the shortest queue from them. You will be surprised to know that these 'power of d choice' policies (JSQ(d) or JSW(d)) perform remarkably well.
Now imagine d-1 friends have tagged along with you at DMart and you are already late for a movie. How do you get out of the payment counters quickly? Welcome to redundancy based load balancing! All d of you join separate queues. The one reaching the head of a payment counter first makes the payment and you are out quicker! What you did is to use redundant copies to implement JSW(d) without having to actually guess the basket sizes.
Beyond supermarket, load balancing is quite common in cloud computing, networks, distributed storage systems, healthcare (organ transplants use redundancy listing) and transportation. See below for some recent work on the analysis of redundancy based load balancing systems.
Papers
R. Jinan, A. Badita, T. Bodas and P. Parag, “Load balancing policies without feedback using timed replicas,” Performance Evalutation, 2023. (pdf, slides)
U. Ayesta, T. Bodas, J.P. Dorsman and I.M. Verloop, “Token based queues with Order-Independent departure rates,” INFORMS Operations Research, 2022. (pdf, video)
T. Hellemans, T. Bodas, and B. Van Houdt, “Performance analysis of workload dependent load balancing policies,” ACM Journal POMACS vol 3, pg 1 - 35, June 2019 (also presented at ACM SIGMETRICS 2019). (pdf, slides)
U. Ayesta, T. Bodas and I.M. Verloop, “A unifying product-form framework for redundancy models,” Performance Evaluation, vol 127, pg 93-119, 2018. (pdf, slides)
U. Ayesta, T. Bodas and I.M. Verloop, “On redundancy-d with cancel-on-start a.k.a Join-shortest-work (d),” MAMA 2018 (SIGMETRICS workshop), Irvine, California, USA. (pdf, slides)
Covert Queueing
Description
Suppose Startup W (for Wille) enters into a contract with a cloud computing platform B (for Bob) for exclusive use of some cloud resources. As part of usage statistics, Bob must provide Willie with a weekly report on the utilization level of its resources. Here is where it gets tricky! Bob sees that Willie is under-utilizing the cloud resources and sees a scope to repurpose a fraction p of Willie's resources without her suspecting it (from the weekly usage reports). How large can p be, so that Willie does not detect this fraud with high probability?
The following papers offer a first cut model for such a covert setup with queues.
Papers
A. Yardi and T. Bodas, “A Covert Queueing Problem with Busy Period Statistic,” IEEE Communications Letters, vol 25, No 3, pg 726 - 729, March 2021.(pdf)
A. Yardi, and T. Bodas, “A covert queueing problem with Markovian statistic”, ITW-2021, Japan.(pdf)
Distributed Systems
Description
With explosion in data and computing speed, distributed systems are here to stay! In distributed storage systems (DSS), data is stored across multiple storage devices, probably distributed across the globe. Likewise, in distributed computing systems (like distributed machine learning (DML)), your computing servers are spread all over. Mind you,every now and then some cloud server or a cloud storage device is going to commit a suicide! A key challenge therefore is to make distributed systems robust to such node failures. How? Enter redundancy (again?). In DSS, erasure codes are used to store information redundantly across storage devices. In DML, gradient coding is used to distribute training data across cloud servers (with added redundancy), making them robust to node failures. In the following work, we study the impact of node failures and data redundancy on the performance of such systems.
Papers
T. Hellemans, A. Yardi, and T. Bodas, “Download time analysis for distributed storage systems with node failures”, ISIT-2021, Australia. (pdf)
A. Johri, A. Yardi, and T. Bodas, “Approximate gradient coding for heterogeneous nodes”, ITW-2021, Japan.(pdf, slides)
Pricing and Congestion
Description
Have you been to the passport office in India? They offer two services (queues), ordinary and tatkal (express). Both these services are priced differently. Obviously, the tatkal service comes at a premium and guarantees a lower waiting time. Like me, you may have wondered which service should you take. The passport office may be wondering what should be the revenue optimizing price for the tatkal. This is a classic game theory situation between the three of you -- you, passport office and 'the others'. While the choice of 'the other' customers impact your congestion experience, you are too insignificant to impact them. Such games are called as non-atomic congestion games and are studied in some of the papers listed below (1,2,5,6,7).
A Variation : What if you replace the tatkal queue with a bidding/bribing queue? The higher the bid/bribe you pay, the better is your queue position and faster is your passport issued. What are your thoughts? Will this have a higher revenue than a tatkal queue? Should bribes be legalized? (papers 3 and 4 below touch on this aspect.)
Papers
T. Bodas, A. Ganesh and D. Manjunath, “Pigouvian Tolls and Welfare Optimality with Parallel Servers and Heterogeneous Customers,” Journal of the Indian Institute of Science, 2021.(pdf, slides )
T. Bodas and D. Manjunath, “Revenue maximization in service systems with heterogeneous customers,” European Journal of Operations Research, vol. 278, pg 686-698, 2019. (pdf,slides)
T. Bodas and D. Manjunath, “On Threshold routing in a Service System with Highest-Bidder-First and FIFO Services,” Operations Research Letters, vol 45, pg 488-492, Sept 2017. (pdf, slides)
T. Bodas, M. Ali and D. Manjunath, “A System with a Choice of Highest-Bidder-First and FIFO Services,” ValueTools, Slovakia, 2014. (pdf, slides)
M. Ali, T. Bodas and D.Manjunath, “Optimal and Equilibrium Allocations in a Discriminatory Processor Sharing System,” NETGCOOP 2014, Trento, Italy. (pdf, slides)
T. Bodas and D.Manjunath, “On Load Balancing Equilibria in Multiqueue Systems with MultiClass Traffic,” Proceedings of NETGCOOP 2011, Paris. (pdf, slides)
T. Bodas, A. Ganesh and D.Manjunath, “Load Balancing and Routing Games with Admission Price,” Proceedings of CDC 2011, Florida. (pdf, slides)
Please visit Google Scholar for a complete list.