System and method for matching objects using a cluster-dependent multi-armed bandit

• US 20090043597A1
• Filed: 08/07/2007
• Published: 02/12/2009
• Est. Priority Date: 08/07/2007
• Status: Abandoned Application

• Current Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Pandey, Sandeep, Chakrabarti, Deepayan, Agarwal, Deepak
• Application Number:
  US11/890,957
• Publication Number:
  US 20090043597A1
• Time in Patent Office: Days
• US Class Current: 705/14.100
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0207 Discounts or incentives, e.g. coupons or rebates

Abstract

An improved system and method for matching objects using a cluster-dependent multi-armed bandit is provided. The matching may be performed by using a multi-armed bandit where the arms of the bandit may be dependent. In an embodiment, a set of objects segmented into a plurality of clusters of dependent objects may be received, and then a two step policy may be employed by a multi-armed bandit by first running over clusters of arms to select a cluster, and then secondly picking a particular arm inside the selected cluster. The multi-armed bandit may exploit dependencies among the arms to efficiently support exploration of a large number of arms. Various embodiments may include policies for discounted rewards and policies for undiscounted reward. These policies may consider each cluster in isolation during processing, and consequently may dramatically reduce the size of a large state space for finding a solution.

Claims

1. A computer system for matching objects, comprising:

a cluster-dependent multi-armed bandit engine for matching a set of objects clustered by dependencies to another set of objects in order to determine an overall maximal payoff; and

a storage operably coupled to the cluster-dependent multi-armed bandit engine for storing clusters of dependent objects with associated payoffs.

2. The system of claim 1 further comprising a cluster selector operably coupled to the cluster-dependent multi-armed bandit engine for selecting a cluster of dependent objects from the set of objects clustered by dependencies to match to an object of the another set of objects in order to determine an overall maximal payoff.

3. The system of claim 2 further comprising an object selector operably coupled to the cluster-dependent multi-armed bandit engine for selecting an object from the cluster of dependent objects to match to the object of the another set of objects in order to determine an overall maximal payoff.

4. The system of claim 3 further comprising a payoff analyzer operably coupled to the cluster-dependent multi-armed bandit engine for determining the overall maximal payoff for selecting the object from the cluster of dependent objects to match to the object of the another set of objects.

5. A computer-readable medium having computer-executable components comprising the system of claim 1.

6. A computer-implemented method for matching objects, comprising:

receiving a first set of objects segmented into a plurality of clusters of dependent objects;

matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit; and

outputting payoffs for the plurality of objects and the plurality of clusters to which the plurality of objects belong.

7. The method of claim 6 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises computing a cluster index for each of the plurality of clusters of dependent objects.

8. The method of claim 7 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises selecting a cluster of dependent objects with a highest index value.

9. The method of claim 8 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises selecting an object within the cluster of dependent objects corresponding to an arm with the highest index value.

10. The method of claim 9 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises updating the payoffs for the plurality of objects and the plurality of clusters to which the plurality of objects belong.

11. The method of claim 6 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises selecting a cluster from the plurality of clusters of dependent objects.

12. The method of claim 11 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises selecting an object within the cluster from the plurality of clusters of dependent objects.

13. The method of claim 12 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises sampling the object within the cluster from the plurality of clusters of dependent objects to receive a reward.

14. The method of claim 13 wherein matching the plurality of objects from the plurality of clusters of dependent objects to the plurality of objects from the second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using the multi-armed bandit comprises updating a payoff for the object within the cluster from the plurality of clusters of dependent objects and a payoff for the cluster from the plurality of clusters of dependent objects.

15. A computer-readable medium having computer-executable instructions for performing the method of claim 6.

16. A computer system for matching objects, comprising:

means for receiving a first set of objects segmented into a plurality of clusters of dependent objects;

means for matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit; and

means for outputting payoffs for the plurality of objects and the plurality of clusters to which the plurality of objects belong.

17. The computer system of claim 16 wherein means for matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit comprises means for selecting a cluster from the plurality of clusters of dependent objects.

18. The computer system of claim 17 wherein means for matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit comprises means for selecting an object within the cluster from the plurality of clusters of dependent objects.

19. The computer system of claim 18 wherein means for matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit comprises means for updating a payoff for the object within the cluster from the plurality of clusters of dependent objects.

20. The computer system of claim 18 wherein means for matching a plurality of objects from the plurality of clusters of dependent objects to a plurality of objects from a second set of objects by sampling the plurality of objects from the plurality of clusters of dependent objects using a multi-armed bandit comprises means for updating a payoff for the cluster from the plurality of clusters of dependent objects.