Optimal Search Problems

One active area of research within STOR-i is the problem of how to optimally search for something or someone. This is a problem of practical importance with it being used for many real world applications. Bomb disposal squads need to search for unexploded ordinance, search parties want to look for survivors of disasters and the police want to find people on the run from the law.

Like most things the best way to build intuition to a problem is to start by constructing smaller toy models of the system. We can represent the places where an object might be hidden as arcs in a network which are connected to each other with nodes. This type of structure is deliberately similar to that of a road system, the arcs represent streets and the nodes are the street corners. The object that we want to find will be hidden along one of the streets and the job of those searching is to find it as quickly as possible.


Example Network for Optimal Searches

See More…

Multi-Armed Bandits

One of the classic problems in Statistics that a lot of people working at STOR-i in particular are involved with is something called ‘Multi-Armed Bandits’. In fact there was a recent conference on the topic and its applications at Lancaster earlier this year. In this post I will try to explain what the problem is and touch on how it is solved.

Originally this problem was first thought about in the casinos of Las Vegas. It concerns how to pick which slot machine out of a group you should play to try in order to try and┬ámaximise your total winnings. Whilst this problem is no longer just applicable to casinos, the name ‘one-armed bandit‘ has stuck and the casino analogy is what I will continue to use.