Project Grant 2149617

COLLABORATIVE RESEARCH: CIF: SMALL: SEQUENTIAL DECISION MAKING UNDER UNCERTAINTY WITH SUBMODULAR REWARDS -MANY COMPANIES, GOVERNMENT AGENCIES, AND INDIVIDUALS MAKE SEQUENCES OF CHALLENGING DECISIONS OVER TIME, FOR WHICH THEY MUST CHOOSE FROM AMONG MANY POSSIBLE OPTIONS, MAY HAVE LIMITED KNOWLEDGE ABOUT THE OUTCOMES OF THEIR DECISIONS, AND WILL RECEIVE LIMITED FEEDBACK. FOR EXAMPLE, SEARCH ENGINES AND CONTENT PROVIDERS MAKE DECISIONS FOR WHAT SETS OF WEBSITES, PRODUCTS, OR MEDIA TO RECOMMEND EACH TIME A USER LOGS ON TO THEIR SYSTEM OR SUBMITS A QUERY, IN SOME CASES HAVING LIMITED KNOWLEDGE OF THE USERS? UNDERLYING PREFERENCES. IF USERS' PRIVACY IS PROTECTED, THEN ONLY USERS' PAST ACTIONS, SUCH AS WHICH LINKS OR MEDIA WERE SELECTED BY EARLIER USERS, WILL BE AVAILABLE AS FEEDBACK TO INFORM THE SEARCH ENGINE OR CONTENT PROVIDER ON WHAT TO RECOMMEND NEXT. THIS PROJECT AIMS TO DEVELOP PROVABLY GOOD STRATEGIES THAT DECISION MAKERS CAN USE IN SUCH SETTINGS, AIDING THEIR DECISION MAKING UNDER UNCERTAINTY AND WITH LIMITED FEEDBACK. THIS PROJECT WILL ALSO DEVELOP STRATEGIES FOR THE MORE CHALLENGING SETTING WHERE MULTIPLE DECISION MAKERS MUST COORDINATE WITH EACH OTHER ON SUCH PROBLEMS, BUT HAVE LIMITED COMMUNICATION AVAILABLE TO DO SO. FURTHERMORE, THIS PROJECT WILL SUPPORT UNDERGRADUATE AND GRADUATE RESEARCH TRAINING, AS WELL AS GRADUATE-LEVEL COURSE DEVELOPMENT, IN MACHINE LEARNING AND ARTIFICIAL INTELLIGENCE, PREPARING STUDENTS FOR CAREERS IN ADVANCED TECHNICAL FIELDS. THE GOAL OF THIS PROJECT IS TO DEVELOP NOVEL, PROVABLY GOOD STRATEGIES FOR SOLVING SEQUENTIAL DECISION PROBLEMS (MULTI-ARMED BANDIT PROBLEMS) WHEN THE ACTIONS AVAILABLE HAVE A COMBINATORIAL STRUCTURE (SUCH AS CHOOSING SUBSETS OF PRODUCTS TO RECOMMEND), THE REWARDS HAVE A DIMINISHING RETURNS PROPERTY (SUBMODULARITY), AND THERE IS NO SIDE-INFORMATION AVAILABLE -- THE ONLY FEEDBACK COMES FROM THE REWARD ITSELF. THE PROPOSED WORK BUILDS ON THE RICH LITERATURE OF MULTI-ARMED BANDITS AND OF SUBMODULAR OPTIMIZATION. THE TECHNICAL AIMS OF THE PROJECT ARE DIVIDED INTO TWO THRUSTS. THE FIRST THRUST FOCUSES ON DEVELOPING ALGORITHMS AND IDENTIFYING THEIR REGRET BOUNDS FOR COMBINATORIAL MULTI-ARMED BANDIT PROBLEMS WITH SUBMODULAR REWARDS AND NO ADDITIONAL FEEDBACK. THE SECOND THRUST EXTENDS THOSE STRATEGIES AND REGRET ANALYSES TO A DECENTRALIZED SETTING, WHERE MULTIPLE AGENTS COORDINATE TO SOLVE COMBINATORIAL MULTI-ARMED BANDIT PROBLEMS, DESPITE LIMITED RESOURCES FOR COMMUNICATION. THIS AWARD REFLECTS NSF'S STATUTORY MISSION AND HAS BEEN DEEMED WORTHY OF SUPPORT THROUGH EVALUATION USING THE FOUNDATION'S INTELLECTUAL MERIT AND BROADER IMPACTS REVIEW CRITERIA.