Improving PAC Exploration Using the Median Of Means

2016-12-01 · NeurIPS 2016 12 · Jason Pazis, Ronald E. Parr, Jonathan P. How

We present the first application of the median of means in a PAC exploration algorithm for MDPs. Using the median of means allows us to significantly reduce the dependence of our bounds on the range of values that the value function can take, while introducing a dependence on the (potentially much smaller) variance of the Bellman operator. Additionally, our algorithm is the first algorithm with PAC bounds that can be applied to MDPs with unbounded rewards.

📄 PDF Abstract BibTeX

Code (0)

등록된 구현이 없습니다.

Robust Marine Buoy Placement for Ship Detection Using Dropout K-Means

2020-01-02 · Yuting Ng, João M. Pereira, Denis Garagic, Vahid Tarokh

Marine buoys aid in the battle against Illegal, Unreported and Unregulated (IUU) fishing by detecting fishing vessels in their vicinity. Marine buoys, however, may be disrupted by natural causes and buoy vandalism. In th…

Clustering

Near-optimal Algorithms for Explainable k-Medians and k-Means

2021-07-02 · Konstantin Makarychev, Liren Shan

We consider the problem of explainable $k$-medians and $k$-means introduced by Dasgupta, Frost, Moshkovitz, and Rashtchian~(ICML 2020). In this problem, our goal is to find a threshold decision tree that partitions data …

Median of Means Sampling for the Keister Function

2025-01-13 · Bocheng Zhang

This study investigates the performance of median-of-means sampling compared to traditional mean-of-means sampling for computing the Keister function integral using Randomized Quasi-Monte Carlo (RQMC) methods. The resear…

Numerical Integration

Median evidential c-means algorithm and its application to community detection

2015-01-07 · Kuang Zhou, Arnaud Martin, Quan Pan, Zhun-Ga Liu

Median clustering is of great value for partitioning relational data. In this paper, a new prototype-based clustering method, called Median Evidential C-Means (MECM), which is an extension of median c-means and median fu…

Clustering Community Detection Graph Clustering Prototype Selection

Hardness of Approximation of Euclidean $k$-Median

2020-11-09 · Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal

The Euclidean $k$-median problem is defined in the following manner: given a set $\mathcal{X}$ of $n$ points in $\mathbb{R}^{d}$, and an integer $k$, find a set $C \subset \mathbb{R}^{d}$ of $k$ points (called centers) s…