skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Optimistic Gittins Indices
We propose a tightening sequence of optimistic approximations to the Gittins index in “Optimistic Gittins Indices.” We show that the use of these approximations in concert with the use of an increasing discount factor appears to offer a compelling alternative to state-of-the-art index schemes proposed for the Bayesian multiarmed bandit problem. We prove that the use of these optimistic indices constitutes a regret optimal algorithm. Perhaps more interestingly, the use of even the loosest of these approximations appears to offer substantial performance improvements over state-of-the-art alternatives while incurring little to no additional computational overhead relative to the simplest of these alternatives.  more » « less
Award ID(s):
1727239
PAR ID:
10584913
Author(s) / Creator(s):
;
Publisher / Repository:
INFORMS
Date Published:
Journal Name:
Operations Research
Volume:
70
Issue:
6
ISSN:
0030-364X
Page Range / eLocation ID:
3432 to 3456
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Small mammals are important to the functioning of ecological communities with changes to their abundances used to track impacts of environmental change. While capture–recapture estimates of absolute abundance are preferred, indices of abundance continue to be used in cases of limited sampling, rare species with little data, or unmarked individuals. Improvement to indices can be achieved by calibrating them to absolute abundance but their reliability across years, sites, or species is unclear. To evaluate this, we used the US National Ecological Observatory Network capture–recapture data for 63 small mammal species over 46 sites from 2013 to 2019. We generated 17,155 absolute abundance estimates using capture–recapture analyses and compared these to two standard abundance indices, and three types of calibrated indices. We found that neither raw abundance indices nor index calibrations were reliable approximations of absolute abundance, with raw indices less correlated with absolute abundance than index calibrations (raw indices overall R2 < 0.5, index calibration overall R2 > 0.6). Performance of indices and index calibrations varied by species, with those having higher and less variable capture probabilities performing best. We conclude that indices and index calibration methods should be used with caution with a count of individuals being the best index to use, especially if it can be calibrated with capture probability. None of the indices we tested should be used for comparing different species due to high variation in capture probabilities. Hierarchical models that allow for sharing of capture probabilities over species or plots (i.e., joint-likelihood models) may offer a better solution to mitigate the cost and effort of large-scale small mammal sampling while still providing robust estimates of abundance. 
    more » « less
  2. Bragg gratings offer high-performance filtering and routing of light on-chip through a periodic modulation of a waveguide’s effective refractive index. Here, we model and experimentally demonstrate the use of Sb2Se3, a nonvolatile and transparent phase-change material, to tune the resonance conditions in two devices which leverage periodic Bragg gratings—a stopband filter and Fabry-Perot cavity. Through simulations, we show that similar refractive indices between silicon and amorphous Sb2Se3can be used to induce broadband transparency, while the crystalline state can enhance the index contrast in these Bragg devices. Our experimental results show the promise and limitations of this design approach and highlight specific fabrication challenges which need to be addressed in future implementations. 
    more » « less
  3. Abstract This article analyzes various color quantization methods using multiple image quality assessment indices. Experiments were conducted with ten color quantization methods and eight image quality indices on a dataset containing 100 RGB color images. The set of color quantization methods selected for this study includes well-known methods used by many researchers as a baseline against which to compare new methods. On the other hand, the image quality assessment indices selected are the following: mean squared error, mean absolute error, peak signal-to-noise ratio, structural similarity index, multi-scale structural similarity index, visual information fidelity index, universal image quality index, and spectral angle mapper index. The selected indices not only include the most popular indices in the color quantization literature but also more recent ones that have not yet been adopted in the aforementioned literature. The analysis of the results indicates that the conventional assessment indices used in the color quantization literature generate different results from those obtained by newer indices that take into account the visual characteristics of the images. Therefore, when comparing color quantization methods, it is recommended not to use a single index based solely on pixelwise comparisons, as is the case with most studies to date, but rather to use several indices that consider the various characteristics of the human visual system. 
    more » « less
  4. Secure multi-party computation (MPC) techniques can be used to provide data privacy when users query deep neural network (DNN) models hosted on a public cloud. State-of-the-art MPC techniques can be directly leveraged for DNN models that use simple activation functions (AFs) such as ReLU. However, these techniques are ineffective and/or inefficient for the complex and highly non-linear AFs used in cutting-edge DNN models. We present Compact, which produces piece-wise polynomial approximations of complex AFs to enable their efficient use with state-of-the-art MPC techniques. Compact neither requires nor imposes any restriction on model training and results in near-identical model accuracy. To achieve this, we design Compact with input density awareness, and use an application specific simulated annealing type optimization to generate computationally more efficient approximations of complex AFs. We extensively evaluate Compact on four different machine-learning tasks with DNN architectures that use popular complex AFs silu, gelu, and mish. Our experimental results show that Compact incurs negligible accuracy loss while being 2x-5x computationally more efficient than state-of-the-art approaches for DNN models with large number of hidden layers. Our work accelerates easy adoption of MPC techniques to provide user data privacy even when the queried DNN models consist of a number of hidden layers, and trained over complex AFs. 
    more » « less
  5. Due to increasing data sparsity in scientific data sets and pruned neural networks, it becomes more challenging to compute with these kinds of sparse data sets efficiently. Several works discuss efficient sparse matrix-vector multiplication (SpMV). However, because of index irregularity in compact stored matrices, sparse matrix-vector multiplication (SpGEMM) still suffers from the trade-off between space and efficiency of computation. In this work, we propose PrGEMM, a multiple reduction scheme which (1) computes SpGEMM under compact storage format without expansion of the operands, (2) by using index lookahead, computes and compares multiple index-data pairs at the same time with no order violation of indices. We evaluate our work with the matrices with different sizes in the SuiteSparse data set. Our work can achieve 3.3x of execution cycle improvement compared to the state-of-the-art SpGEMM scheme. 
    more » « less