Collaborative Research: Adaptive Allocation Rules in High-Dimensional Settings, with Applications

本项目的研究目标是研究自适应资源分配中的问题，其中可用动作的数量非常大或无限。在这些问题中，决策者在每个时间步选择一个行动，并观察一些回报，但这些回报的分配最初是未知的。信息是在决策过程中获得的。这引入了一种权衡，一是选择在现有信息下看起来最有利可图的行动，二是选择能带来有关未探索可能性的额外信息的行动。这项研究将制定和研究一个新的模型，其中不同行动的回报不是相互独立的，而是由少量潜在的随机变量决定的。通过利用奖励之间的相关性，这项研究将开发出快速确定最佳行动的策略。本项目中开发的模型和策略将应用于网络广告、价格优化和供应链管理等问题。如果成功，该项目将产生在许多应用中立即有用的新方法。这项研究还将通过制定后悔的下限和达到(或几乎达到)下限的政策，确定在此类模型中可以获得的最佳后悔和风险(作为时间和潜在变量数量的函数)。此外，该项目将产生涉及非平稳环境的新框架，并与自适应随机控制中的经典问题建立联系。这项工作将为一些重要的自适应决策问题提供一个新的视角，包括该领域的一些新的公式和方向。

The research objective of this project is the study of problems in adaptive resource allocation, where the number of available actions is very large or infinite. In these problems, the decision maker chooses an action at each time step and observes some rewards, but the distribution of these rewards is initially unknown. Information is acquired during the decision making process. This introduces a tradeoff between choosing actions that appear most profitable given the available information, and choosing actions that result in additional information on unexplored possibilities. The research will formulate and study a new model, where the rewards of different actions are not independent of each other, but are determined by a small number of underlying random variables. By exploiting the correlation among the rewards, this research will develop policies that quickly identify the optimal action. The models and polices developed in this project will be applied to problems such as web advertising, price optimization, and supply chain management. If successful, the project will result in novel methodologies with immediate usefulness in many applications. The research will also establish the best possible regret and risk that can be attained in such models (as a function of time and of the number of underlying variables), by developing lower bounds on regret and policies that achieve (or nearly achieve) the lower bounds. In addition, the project will result in novel frameworks involving non-stationary environments, and establish a connection with classical problems in adaptive stochastic control. This work will provide a new perspective on some important classes of adaptive decision making problems, including some novel formulations and directions in this field.