Online collaborative filtering with nearly optimal dynamic regret

ABSTRACT

We consider a model for sequential online decision-making by many diverse agents. On each day, each agent makes a decision, and pays a penalty if it is a mistake. Obviously, it would be good for agents to avoid repeating the same mistakes made by other agents; however, difficulty may arise when some agents disagree over what constitutes a mistake, perhaps maliciously.

As a metric of success for this problem, we consider dynamic regret, i.e., regret versus the off-line optimal sequence of decisions. Previous regret bounds usually use the much weaker notion of static regret, i.e., regret versus the best single decision in hindsight. We assume there is a set of "honest" players whose valuations for the decisions at each time step are identical. No assumptions are made about the remaining players, and the algorithm assumes no information about which are the honest players.

We present an algorithm for this setting whose expected dynamic regret per honest player is optimal up to a multiplicative constant and an additive polylogarithmic term, assuming the number of options is bounded.

REFERENCES

• 1: Noga Alon , Baruch Awerbuch , Yossi Azar , Boaz Patt-Shamir, Tell me who I am: an interactive recommendation system, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148111]
• 2: B. Awerbuch and C. Scheideler. Enforced Spreading: An improved protocol for provably secure distributed name service. Technical report, Johns Hopkins University, February 2004.
• 3: B. Awerbuch and C. Scheideler. Group Spreading: A protocol for provably secure distributed name service. In proc 31st ICALP, 2004.
• 4: Baruch Awerbuch , Yossi Azar , Zvi Lotker , Boaz Patt-Shamir , Mark R. Tuttle, Collaborate with strangers to find own preferences, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074014]
• 5: Baruch Awerbuch, David Holmer, Herbert Rubens, and Robert Kleinberg. Provably competitive adaptive routing. In Infocom. IEEE, 2005.
• 6: Baruch Awerbuch and Robert Kleinberg. Collaborative learning. In Proceedings ACM COLT (Computational Learning Theory), 2005.
• 7: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Collaboration of untrusting peers with changing interests, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988789]
• 8: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Adaptive Collaboration in Peer-to-Peer Systems, Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS'05), p.71-80, June 06-10, 2005 [doi>10.1109/ICDCS.2005.9]
• 9: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Improved recommendation systems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 10: Baruch Awerbuch and Christian Scheideler. Robust distributed name service. In Proc. of 3rd International Workshop on Peer-to-Peer Systems (IPTPS), feb 2004.
• 11: Baruch Awerbuch , Christian Scheideler, Towards a scalable and robust DHT, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148163]
• 12: Baruch Awerbuch and Christian Scheideler. Robust random number generation for peer-to-peer systems. In In Proc. ACM OPODIS, 2007.
• 13: Baruch Awerbuch and Christian Scheideler. Towards scalable and robust overlay networks. In Proceedings of IPTPS, 2007.
• 14: J. M. Barzdin and R. V. Freivalds. On the prediction of general recursive functions. Soviet Mathematics Doklady, 13:1224--1228, 1972.
• 15: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Algorithms, Theory

Keywords:
collaborative filtering, learning, multiagent systems, online decision making, regret