Learning to Compete in Heterogeneous Web Search Environments

1 Introduction

Previous research in Web search has mainly targeted perfor­ mance of search engines from the user's point of view. Pa­ rameters such as precision, recall, and freshness of returned results were optimised. On the other hand, a provider of search services is rather interested in parameters like the num­ ber of queries processed versus the amount of resources used to process them. We focus on performance optimisation of search engines from the service provider's point of view.

An important factor that affects the search engine perfor­ mance is competition with other independently controlled search engines. When there are many engines available, users want to send queries to those that provide the best possible results. Thus, the service offered by one search engine influ­ ences queries received by others.

Competition is even more important in heterogeneous search environments consisting of many specialised search engines (which provide access to the so-called "deep" or "in­ visible" Web). Each specialised engine in such environment indexes only a subset of all documents (e.g. on a particular topic). Each user query is only sent to a small number of the engines which can return the best results. Selection be­ tween specialised search engines is done (semi)automatically by meta-searchers, which rank engines for each user query. Thus, parameters of specialised engines automatically affect their ranking and, hence, the queries they receive, and ulti­ mately their profit.

We are examining the problem of performance-maximising behaviour for non-cooperative specialised search engines in heterogeneous search environments. In particular, we analyse how specialised search engines can select on which topic(s) to specialise and how many documents to index on that topic. We provide a game-theoretic analysis of a simplified ver­ sion of the problem and motivate the use of the concept of "bounded rationality". Bounded rationality assumes that decision makers are unable to act optimally in the game­ theoretic sense due to incomplete information about the en­ vironment and/or limited computational resources. We then cast our problem as a reinforcement learning task, where the goal of a specialised search engine is to exploit sub-optimal behaviour of its competitors to improve own performance.

*This research was funded by Science Foundation Ireland and the US Office ofNaval Research.

Decision making process. For each time interval, the search engines simultaneously and independently decide on how many documents to index and allocate resources to pro­ cess expected search queries (thus incurring the correspond­ ing costs). As search engines cannot have unlimited crawling resources, we presume that they can only do incremental ad­ justments to their index contents that require the same time for all engines. The user queries are allocated to the engines based on their index parameters (Df) as described above.

Since a search engine cannot know the number of queries that users will submit, it may allocate less query processing resources than the number of queries it will receive. We as­ sume that excess queries are discarded and the search engine does not benefit from them. Then, performance of engine i over a given time interval can be represented as

where Qi = I:t:D'>O Q~ is the expected number of queries across all topics for' which the search engine is trying to com­ pete (i.e. index at least one document), Di = L:t D~ is the total number of indexed documents, Q; = L:t Q~ is the total number of queries actually received by engine i, and

is the share of queries in topic t received by engine i, and Qt is the number of queries users submitted on topic t.

3 Analysis and Solution Approach

The decision-making process can be modelled as a multi­ stage game. At each stage, a matrix game is played, where players are search engines, actions are values of (Df), and player i receives payoff Pi (as above). If player i knew the actions of its opponents at a future stage k, it could calculate the optimal response as the one maximising its payoff Pi(k) at that stage. For example, in case of a single topic and a con­ stant query stream it should play Di(k) = max#i D1(k) + 1, ifmax#i D1(k) + 1 <a/ {3 , and Di(k) = 0 otherwise (sim­ ply put, outperform opponents by 1 document if profitable, and do not incur any costs otherwise).

In reality, the players do not know the future. One possible way around this would be to agree on (supposedly, mutually beneficial) actions in advance. To avoid deception, players would have to agree on playing a Nash equilibrium of the game, since only then there will be no incentive for them to not follow the agreement. Agreeing to play a Nash equilib­ rium, however, becomes problematic when the game has mul­ tiple such equilibria. Players would be willing to agree on a Nash equilibrium yielding to them the highest (expected) payoffs, but the task of characterising all Nash equilibria of a game is NP-hard even given complete information about the game (as follows from [Conitzer and Sandholm, 2002]).

NP-hardness results and the possibility that players may not have complete information about the game lead to the idea of "bounded rationality", when players may not use the optimal strategies in the game-theoretic sense. Our proposal is to cast the problem of optimal behaviour in the game as a learning task, where the player would have to learn a strategy that performs well against its sub-optimal opponents.

Learning in repeated games has been studied extensively in game theory and machine learning. Examples include fictious play and opponent modelling [Robinson, 1951; Carmel and Markovitch, 1996]. We apply a more recent algorithm from reinforcement learning called GAPS [Peshkin eta!. , 2000]. In GAPS, the learner plays a parameterised strategy repre­ sented by a finite state automaton, where the parameters are the probabilities of actions and state transitions. GAPS im­ plements stochastic gradient ascent in the space of policy pa­ rameters. After each learning trial, parameters of the policy are updated by following the payoff gradient.

GAPS has a number of advantages important for our do­ main. It works in partially observable games. It also scales well to multiple topics by modelling decision-making as a game with factored actions (where action components corre­ spond to topics). The action space in such games is the prod­ uct of factor spaces for each action component. GAPS, how­ ever, allows us to reduce the learning complexity: rather than learning in the product action space, separate GAPS learners can be used for each action component. It has been shown that such distributed learning is equivalent to learning in the product action space. We call a search engine that uses the proposed approach COUGAR, which stands for COmpetitor Using GAPS Against Rivals.

4 Preliminary Results

We evaluated our approach in a number of simulation exper­ iments, which demonstrated COUGAR's ability to compete successfully with different opponents. For the sake of brevity, we present here results from one such experiment with two competing search engines. One search engine was using a fixed strategy, called "Bubble", the other one was COUGAR. The search engines could increase, decrease (by one), or keep the number of documents indexed on each topic. They could also observe the size of own index, the relative sizes of oppo­ nents' indices, and the number of user queries Qt submitted for each topic (the last two observations can be obtained from the meta-searcher). The expected number of queries on topic tat future stage k was calculated as QHk) = Qt(k- 1).

The experimental setup consisted of three components: the generator of search queries, the metasearcher, and the search engines. The state of a search engine's document index is represented by a vector (Df) of the numbers of documents indexed by the search engine for each topic. This is the infor­ mation used by the metasearcher to select search engines.

To simulate user search queries, we used HTTP logs ob­ tained from a Web proxy of a large ISP. We developed extrac­ tion rules individually for 4 7 well-known search engines. The total number of queries extracted was 657,861 collected over a period of 190 days. We associated topics with search terms in the logs. To simulate queries for T topics, we extracted the T most popular terms from the logs. The number of queries generated on topic t for a given day was equal to the number of queries with term t in the logs belonging to this day.

The "Bubble" strategy tries to index as many documents as possible without any regard to what competitors are doing. As follows from our performance formula (Section 2), such unconstrained growing leads eventually to negative per­ formance. Once the total reward falls below a certain thresh­ old, the "Bubble" search engine goes bankrupt (it shrinks its index to 0 documents and retires until the end of the trial). This process imitates the situation, in which a search provider expands its business without paying attention to costs, and eventually runs out of money (or an analogy with the "_ corn bubble")- An intuitively sensible response to the "Bubble" strategy would be to wait until the bubble "bursts" and then come into the game alone. That is, a competitor should not index anything while the "Bubble" grows and should start in­ dexing a minimal number of documents once the "Bubble" search engine goes bankrupt Our simulation had two topics, and "Bubble" was increas­ ing (and decreasing) the number of documents indexed for each topic simultaneously. First, we trained COUGAR in a number of learning trials. Once it reached a steady perfor­ mance level, the resulting strategy was evaluated in a series of testing trials. Each simulation trial consists of 100 days, where each day corresponds to one stage of the multi-stage game played. The resulting performance in the whole trial is calculated as a sum of discounted rewards from each day.

Figure 1 shows how COUGAR's performance improving during learning. Figure 2 visualises a testing trial between the "Bubble" and the COUGAR engines by showing the num­ ber of documents indexed by the engines on each day of the trial (the top half of Y axis shows the number of documents for topic 1, the bottom half shows the number of documents for topic 2). Note that COUGAR has learned to wait until "Bubble" goes bankrupt, and then to win all queries for both topics.

We also investigated effectiveness of our approach against evolving opponents. In particular, we evaluated performance of a COUGAR strategy learned in self-play against other learners (other COUGARs in our case). We observed that while COUGAR's performance can be quite stable against equally complex learners, it may still be sub-optimal, in the sense that a "cleverer" Ieamer (e.g. a COUGAR with more policy states) can outperform it

5 Future Work

We do not claim to provide a complete solution for the problem of performance management in heterogeneous Web search, but COUGAR is a promising first step. Clearly, we have made many strong assumptions in our models. One future direction will be to relax these assumptions to make our simulations more realistic. Another important direction would be to further study performance of the learning algo­ rithm in self-play, as well as against other learners.

While we are motivated by the optimal behaviour for search services over document collections, our approach is applicable in more general scenarios involving services that must weigh the cost of their inventory of objects against the expected inventories of their competitors and the anticipated needs of their customers. For example, it would be interest­ ing to apply our ideas to large retail e-commerce sites which must decide what products to stock.