Self-awareness, Self-expression and Meta-self-awareness in the Relevant Neighbourhood Selection Problem

Peter R. Lewis and Xin Yao
Technical report CSR-12-02, University of Birmingham, School of Computer Science. September 2012.

In this report we introduce the relevant neighbourhood selection problem, a parallel online reinforcement learning problem under uncertainty, with high relevance to practical applications of self-aware collective systems composed of multiple self-interested agents. Firstly, we motivate and clearly formulate the problem framework, before discussing approaches for specifying particular instantiations of the problem, including a proposed model of uncertainty. We subsequently introduce a socially-inspired heuristic solution technique, based on ant pheromones. We present experimental results on some baseline problem instances, comparing our proposed approach with existing state-of-the-art techniques ported from the related multi-armed bandit problem. We show that none of the solution techniques presented dominates all others across the range of problem instances considered, even those techniques which are so simplistic as to make no use of observed online performance. This motivates the use of online meta-self-aware strategy selection, which we demonstrate using the epsilon-greedy strategy to balance exploration and exploitation. We compare the relative performance of nodes which do and do not engage in this form of meta-level strategy selection, showing that the value of meta-self-awareness depends on the particular scope of adaptation being considered.

author = "Peter R. Lewis and Xin Yao",
title = {Self-awareness, Self-expression and Meta-self-awareness in the Relevant Neighbourhood Selection Problem},
institution = {University of Birmingham, School of Computer Science},
number = {CSR-12-02},
month = {September},
year = {2012},
url = {},