Long's profile picture

Sequential decision making

My primal research area is sequential decision making with constraints. More precisely, I am interested in multi-armed bandit (MAB) models where pulling an arm (i.e., making a decision) requires a cost and the total spending is limited by a finite budget. To tackle this problem, I have introduced a new model, called the budget-limited MAB, and have also proposed a number of arm pulling algorithms for which I have provided both theoretical and empirical performance analyses. For more details, see:

  • AAAI 2010 paper
  • AAAI 2012 paper (honourable mention for the AAAI 2012 Outstanding Paper Award)
  • My PhD thesis (runner-up for the best European PhD thesis in AI, and runner-up for the best Computer Science PhD thesis in the UK)
I am also interested in applying this bandit model (or its variances) to other domains of AI, such as

  • Decentralised controlling for UAVs: AAMAS 2012 paper
  • Information collection in wireless sensor networks: JAAMAS journal article
  • Budget-limited online keyword bidding: UAI 2014 paper


Game theory

I mainly focus on large coalition formation games from both game theoretical and decision making perspective. In more detail, I look at systems where the number of participants is very large (typically thousands or more). Within these systems, calculating different solution concepts (e.g., the core, nucleolus, Shapley-value, etc.) are very hard. Given this, my goal is to identify approximation techniques that can efficiently provide high quality results. To do so, with some of my colleagues, we have introduced a novel, vector-based, representation model of the participating agents, with which we can calculate the abovementioned concepts in a significantly more efficient way. For more details, see our IJCAI 2013 paper.

We have also analysed the error bounds of approximating the Shapley value in large games. See our working paper.

Staying within game theory, I also study different games with resource allocation from both aspects of classical and behaviourial game theory. In particular, I am interested in calculating different equilibria and price of anarchy. A preliminary version of work has been published at SAGT 2011.

From the behaviourial game theory perspective, I aim to identify players' favourite strategies when they repeatedly play such games against different opponents (Repeated Colonel Blotto).


Crowdsourcing

More recently, I investigate the performance of different crowdsourcing systems from a theoretical perspective, aiming to provide rigorous performance guarantees for task allocation algorithms. Some of our works are listed below:

  • ECAI 2012 paper (runner-up for the ECAI 2012 Best Student Paper Award)
  • AAMAS 2013 paper
  • AAMAS 2014 paper
  • AAAI 2015 paper
  • AIJ journal article


Home energy management

I am heavily involved in the research work on home energy management. In particular, we aim to improve the energy consumption profile of home owners, in order to reduce the CO2 emission of the domestic energy sector. To do so, as the first step, we mainly focussed on the accurate learning and prediction of homeowners' habit, such as appliance usage and heating preferences. Some of work currently published works can be found here:


Other research interests

The cost of interference to closed evolving systems: We investigate what is the cost to interfere into closed systems, if we want the system to achieve some desirable states. As a first step, we look at evolving evolutionay games, where an external decision maker can invest his resources into the system (e.g., via a reward scheme) such that in the long term, the agents will follow a prefered behaviour. A preliminary result has been presented at COIN 2014 and NAG 2014.

Stochastic shortest path problems: This is an ongoing work on approximating the classical stochastic shortest path, defined by Frank (1969). In particular, so far I have developed a new concentration inequality that provides a lower bound on the probability mass of the lower-tail (i.e., a lower bound on the probability P(X < a) with a < E[X]). Combining this new result with other existing concentration bounds, I could provide a O(n^3) running time algorithm that can achieve O(1/n) approximation for sure (where n is the number of vertices). In addition, the algorithm works for any type of bounded distribution. To the best of my knowledge (which can be obsolete), the scurrent tate of the art is pseudo-polynomial with 2/n approximation coefficent, which only works on discrete distributions. Currently I am aiming to improve the approximation coefficient of my algorithm.

Non-monetary referral incentives: I am also investigating how non-monetary referral incentivisation work in social networks. You can find a preliminary version of our work here. For more details, you can visit the website of our project, or watch a video about it.