Low Complexity Online Contextual Learning with Continuous Actions

We study an online contextual learning problem, where an agent repeatedly observes independent and identically distributed (IID) contexts 𝑐𝑡 ∈ R𝑑 and selects actions 𝑥𝑡 ∈ R𝑘 to maximize its cumulative reward 𝑟(𝑥𝑡, 𝑐𝑡) over 𝑇 rounds. The reward function is Lipschitzcontinuousincontexts, sogoodactionsforagivencontext are also reasonably good for similar contexts. Current algorithms that leverage this structure are practically infeasible due to large runtime or memory complexity. In this paper, we propose Congrad, a simple kernel-based projected gradient ascent algorithm, which maintains𝑂(𝑛) memoryand𝑂(𝑛(𝑘+𝑑)) computationalcomplexity per iteration by projecting policies onto a fixed𝑛-dimensional function space. Congrad utilizes a kernel that at each turn updates the actions for contexts 𝑐 near the observed 𝑐𝑡. The kernel initially has a large bandwidth to enable fast global learning, and progressively narrows for local refinement. We prove an expected regret bound of 𝑂(𝑇 𝑑+1 𝑑+2 ), independent of the action space dimension 𝑘.

Authors

• Mohsen Najjar Tel Aviv University
• Tavor Baharav Broad Institute
• Ilai Bistritz Tel Aviv University

Keywords

• Contextual learning
• Stochastic optimization