Learning a model over possible actions and using the learned model to maximize the obtained reward is an integral part of many applications. Trying to simultaneously learn the model by exploring state space and maximize the obtained reward using the learned model is an exploitation-exploitation tradeoff. Gaussian process upper confidence bound (GB-UCB) algorithm is an effective method for balancing between exploitation and exploration when exploring spatially dependent data in n-dimensional space.
The balance between exploration and exploitation is required to limit the amount of user feedback required to achieve good prediction result in our context-based image retrieval system. The system starts with high amount of exploration and — as the confidence in the model increases — it starts exploiting the gathered information to direct the search towards better results.
While the implementation of the GP-UCB is quite straightforward, it has time complexity of O(n^3) which limits its use in near real-time applications. In this thesis I present our reinforcement learning image retrieval system based on GP-UCB, with the focus on speed requirements for interactive applications. I also show simple methods to speed up the algorithm running time by doing some of the Gaussian process calculations on the GPU.
