Attention:The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, October 15th until 12:00 AM ET on Friday, October 16th due to maintenance. We apologize for the inconvenience.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Active Learning for Contextual Search with Binary Feedback
In this paper, we study the learning problem in contextual search, which is motivated by applications such as crowdsourcing and personalized medicine experiments. In particular, for a sequence of arriving context vectors, with each context associated with an underlying value, the decision maker either makes a query at a certain point or skips the context. The decision maker will only observe the binary feedback on the relationship between the query point and the value associated with the context. We study a probably approximately correct learning setting, where the goal is to learn the underlying mean value function in context with a minimum number of queries. To address this challenge, we propose a trisection search approach combined with a margin-based active learning method. We show that the algorithm only needs to make [Formula: see text] queries to achieve an ε-estimation accuracy. This sample complexity significantly reduces the required sample complexity in the passive setting where neither sample skipping nor query selection is allowed, which is at least [Formula: see text]. This paper was accepted by J. George Shanthikumar, data science.  more » « less
Award ID(s):
1845444
PAR ID:
10376123
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Management Science
ISSN:
0025-1909
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Operations Research)
    In this work, we consider the popular tree-based search strategy within the framework of reinforcement learning, the Monte Carlo tree search (MCTS), in the context of the infinite-horizon discounted cost Markov decision process (MDP). Although MCTS is believed to provide an approximate value function for a given state with enough simulations, the claimed proof of this property is incomplete. This is because the variant of MCTS, the upper confidence bound for trees (UCT), analyzed in prior works, uses “logarithmic” bonus term for balancing exploration and exploitation within the tree-based search, following the insights from stochastic multiarm bandit (MAB) literature. In effect, such an approach assumes that the regret of the underlying recursively dependent nonstationary MABs concentrates around their mean exponentially in the number of steps, which is unlikely to hold, even for stationary MABs. As the key contribution of this work, we establish polynomial concentration property of regret for a class of nonstationary MABs. This in turn establishes that the MCTS with appropriate polynomial rather than logarithmic bonus term in UCB has a claimed property. Interestingly enough, empirically successful approaches use a similar polynomial form of MCTS as suggested by our result. Using this as a building block, we argue that MCTS, combined with nearest neighbor supervised learning, acts as a “policy improvement” operator; that is, it iteratively improves value function approximation for all states because of combining with supervised learning, despite evaluating at only finitely many states. In effect, we establish that to learn an ε approximation of the value function with respect to [Formula: see text] norm, MCTS combined with nearest neighbor requires a sample size scaling as [Formula: see text], where d is the dimension of the state space. This is nearly optimal because of a minimax lower bound of [Formula: see text], suggesting the strength of the variant of MCTS we propose here and our resulting analysis. 
    more » « less
  2. ; ; ; (, International Journal of Computational Geometry & Applications)
    Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let [Formula: see text] and [Formula: see text] be two polygonal curves in [Formula: see text] with [Formula: see text] and [Formula: see text] vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in [Formula: see text] time, (3) a linear-time [Formula: see text]-approximation algorithm, and (4) a data structure that supports [Formula: see text]-time decision queries, where [Formula: see text] is the number of vertices of the query curve and [Formula: see text] the number of vertices of the preprocessed curve. 
    more » « less
  3. ; ; ; (, Mathematics of Operations Research)
    We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SampleGreedy, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-extendible system using [Formula: see text] evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-Streaming, which obtains a [Formula: see text]-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and [Formula: see text] evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks. 
    more » « less
  4. ; ; (, SIAM Journal on Computing)
    Abstract. A [Formula: see text]- vertex connectivity oracle for an undirected graph [Formula: see text] is a data structure that, given [Formula: see text], reports [Formula: see text], where [Formula: see text] is the pairwise vertex connectivity between [Formula: see text]. There are three main measures of efficiency: construction time, query time, and space. Prior work of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43] produced a data structure of [Formula: see text] words, which can even be encoded as a [Formula: see text]-bit labeling scheme, that can answer vertex connectivity queries in [Formula: see text] time. The construction time is polynomial but unspecified. In this paper, we address the top three complexity measures. (1) Space: We prove that any [Formula: see text]-vertex connectivity oracle requires [Formula: see text] bits of space for any [Formula: see text]. This proves that the Iszak–Nutov data structure is optimal up to polylogarithmic factors for every [Formula: see text] and that the sparsifiers of Nagamochi and Ibaraki [ Algorithmica, 7 (1992), pp. 583–596] are optimal compression schemes for [Formula: see text]-vertex connectivity up to a logarithmic factor. In particular, whereas all edge connectivities can be efficiently compressed (as a weighted [Formula: see text]-edge Gomory–Hu tree), vertex connectivity admits no asymptotic compression: [Formula: see text] bits are necessary. We design a variation on Izsak and Nutov’s data structure that uses [Formula: see text] words of space. (2) Query time: We answer queries in [Formula: see text] time, improving on the [Formula: see text] time bound of Izsak and Nutov [ Inform. Process. Lett., 112 (2012), pp. 39–43]. The main idea is to build instances of [Formula: see text] data structures, with additional structure based on affine planes. This structure allows for query time that is linear in the output size, which evades some conditional lower bounds that are polynomial in the query set sizes [ 42 ,  51 ]. (3) Construction time: Our data structure can be constructed in the time of [Formula: see text] max-flow computations, namely, [Formula: see text] time, using the recent near-linear time flow algorithm of [ 13 ]. The main technical contribution here is a fast algorithm to compute a [Formula: see text]-approximate Gomory–Hu tree for element connectivity in the time of [Formula: see text] max-flow computations. Element connectivity is a notion that generalizes edge and vertex connectivity. 
    more » « less
  5. ; ; (, Operations Research)
    We study reinforcement learning (RL) in a setting with a network of agents whose states and actions interact in a local manner where the objective is to find localized policies such that the (discounted) global reward is maximized. A fundamental challenge in this setting is that the state-action space size scales exponentially in the number of agents, rendering the problem intractable for large networks. In this paper, we propose a scalable actor critic (SAC) framework that exploits the network structure and finds a localized policy that is an [Formula: see text]-approximation of a stationary point of the objective for some [Formula: see text], with complexity that scales with the local state-action space size of the largest [Formula: see text]-hop neighborhood of the network. We illustrate our model and approach using examples from wireless communication, epidemics, and traffic. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Text Encoded Conversion
  • XML
  • Save / Share this Record
  • Send to Email