We formulate a new problem at the intersection of semi-supervised learning and contextual bandits, motivated by several applications including clinical trials and dialog systems. We demonstrate how contextual bandit and graph convolutional networks can be adjusted to the new problem formulation. We then take the best of both approaches to develop multi-GCN embedded contextual bandit. Our algorithms are verified on several real world datasets. We formulate the problem of Online Partially Rewarded (OPR) learning. Our problem is a synthesis of the challenges often considered in the semi-supervised and contextual bandit literature. Despite a broad range of practical cases, we are not aware of any prior work addressing each of the corresponding components.Online: data incrementally collected and systems are required to take an action before they are allowed to observe any feedback from the environment.Partially: oftentimes there is no environment feedback available, e.g. a missing label Rewarded: instead of the true label, we can only hope to observe feedback indicating whether our prediction is good or bad (1 or 0 reward), the latter case obscuring the true label for learning.Practical scenarios that fall under the umbrella of OPR range from clinical trials to dialog orchestration. In clinical trials, reward is partial, as patients may not return for followup evaluation. When patients do return, if feedback on their treatment is negative, the best treatment, or true label, remains unknown. In dialog systems, a user's query is often directed to a number of domain specific agents and the best response is returned. If the user provides negative feedback to the returned response, the best available response is uncertain and moreover, users can also choose to not provide feedback.In many applications, obtaining labeled data requires a human expert or expensive experimentation, while unlabeled data may be cheaply collected in abundance. Learning from unlabeled observations is the key challenge of semi-supervised learning BID2 . We note that the problem of online semi-supervised leaning is rarely considered, with few exceptions BID14 BID13 . In our setting, the problem is further complicated by the bandit-like feedback in place of labels, rendering existing semi-supervised approaches inapplicable. We will however demonstrate how one of the recent approaches, Graph Convolutional Networks (GCN) BID9 , can be extended to our setting.The multi-armed bandit problem provides a solution to the exploration versus exploitation tradeoff while maximizing cumulative reward in an online learning setting. In Linear Upper Confidence Bound (LINUCB) BID10 BID4 and in Contextual Thompson Sampling (CTS) BID0 , the authors assume a linear dependency between the expected reward of an action and its context. However, these algorithms assume that the bandit can observe the reward at each iteration. Several authors have considered variations of partial/corrupted rewards BID1 BID6 , but the case of entirely missing rewards has not been studied to the best of our knowledge.The rest of the paper is structured as follows. In section 2, we formally define the Online Partially Rewarded learning setup and present two extensions to GCN to suit our problem setup. Section 3 presents quantitative evidence of these methods applied to four datasets and analyses the learned latent space of these methods.
Synthesis of GCN and LINUCB algorithms for online learning with missing feedbacks
{"src": "scitldr-AIC_train", "paper_id": "HkgrQE7luV"}