Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work \cite{efroni2018beyond}, multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analy…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “greedy policy”
Study on rapid policy changes in reinforcement learning.
problem Rapid change of greedy policy in reinforcement learning.
method Empirical study and ablation analysis.
result Policy churn is a beneficial form of implicit exploration.
We propose a new concept named adaptive submodularity ratio to study the greedy policy for sequential decision making. While the greedy policy is known to perform well for a wide variety of adaptive stochastic optimization problems in practice, its theoretical properties have been analyzed only for a limited class of p…
Greedy policy maximizes information in unknown linear systems.
problem Exploration in unknown linear dynamical systems.
method Online greedy policy maximizing information.
result Competitive performance compared to gradient-based methods.
Enhances PMD with lookahead to improve RL performance.
problem Improving RL performance with greedy policies over 1-step.
method Integrates multi-step greedy policies into PMD with lookahead.
result Shows faster convergence rate for -PMD.
Greedy policies perform poorly in imperfectly observed contextual bandits.
problem Performance of Greedy policies in bandits with partially observed contexts.
method Analysis of Greedy reinforcement learning policies under imperfectly observed contextual bandits.
result Worst-case regret grows poly-logarithmically with the time horizon and the failure probability.
Recent successful deep reinforcement learning algorithms, such as Trust Region Policy Optimization (TRPO) or Proximal Policy Optimization (PPO), are fundamentally variations of conservative policy iteration (CPI). These algorithms iterate policy evaluation followed by a softened policy improvement step. As so, they are…
Greedy AutoAugmentcs.LG
A major problem in data augmentation is to ensure that the generated new samples cover the search space. This is a challenging problem and requires exploration for data augmentation policies to ensure their effectiveness in covering the search space. In this paper, we propose Greedy AutoAugment as a highly efficient se…
Paper analyzes Greedy-GQ for reinforcement learning with Markovian noise.
problem Analyzing Greedy-GQ for reinforcement learning with Markovian noise.
method Develops finite-sample analysis for Greedy-GQ with linear function approximation under Markovian noise.
result Provides theoretical justification for choosing stepsizes for faster convergence.
Optimizes state monitoring in Markovian systems with cost constraints.
problem Balancing state queries with prediction costs in Markovian systems.
method Greedy policy and SGD-based learning variant for optimal predict-query tradeoff.
result Greedy policy is suboptimal but performs close to optimal under certain conditions.
Entropy regularization improves policy optimization in reinforcement learning.
problem Improving policy optimization in reinforcement learning.
method Entropy regularization is introduced to soften the greedy policy towards a more diverse softmax policy, leading to a continuously parameterized algorithm that interpolates between policy gradient and Q-learning.
result An intermediate algorithm can improve performance in reinforcement learning.
New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problemcs.LG
New distributions allow greedy arm selection in sparse bandit problems.
problem Sparse contextual bandit problem with sparse parameters and feature distributions.
method Introduced new distribution classes and demonstrated that mixtures of these distributions are also greedy-applicable.
result Greedy algorithm applicable to a wider range of arm feature distributions, including those with origin-asymmetric support.
Off-policy reinforcement learning with eligibility traces is challenging because of the discrepancy between target policy and behavior policy. One common approach is to measure the difference between two policies in a probabilistic way, such as importance sampling and tree-backup. However, existing off-policy learning …
Paper proposes an -policy gradient for online pricing, reducing regret to .
problem Online pricing learning task
method Combines model-based and model-free reinforcement learning, using -greedy with gradient descent.
result Achieves expected regret of order .
Simple policy search outperforms advanced learnable test-time augmentation techniques.
problem Improving predictive performance through test-time data augmentation.
method Greedy policy search (GPS) for learning test-time augmentation policies.
result Augmentation policies learned with GPS achieve superior predictive performance and robustness.
DSPI connects natural policy gradient to policy iteration, proving global convergence.
problem Optimizing policies in reinforcement learning.
method DSPI framework, combining smoothed policy iteration and natural policy gradient.
result DSPI achieves geometric convergence and optimal complexity for policy optimization.
This paper analyzes the sample complexity of two timescale reinforcement learning algorithms.
problem Analyzing the sample complexity of two timescale reinforcement learning algorithms.
method Non-asymptotic analysis of linear and nonlinear TDC and Greedy-GQ algorithms under Markovian sampling with constant stepsize.
result The paper provides non-asymptotic convergence results for two timescale linear and nonlinear TDC and Greedy-GQ algorithms.
ETGL-DDPG improves DDPG for sparse reward control with new exploration and replay techniques.
problem Sparse reward continuous control in reinforcement learning.
method Introduces -greedy search and GDRB framework for efficient exploration and reward use.
result ETGL-DDPG outperforms DDPG and other methods on sparse-reward continuous benchmarks.
ConQUR tackles delusional bias in deep Q-learning, improving performance in Atari games.
problem Delusional bias in deep Q-learning.
method Efficient methods to mitigate delusional bias by training Q-approximators with consistent labels and a search framework.
result Improves performance in Atari games, sometimes dramatically.
Bayesian approach improves -greedy exploration in RL.
problem Improving -greedy exploration in model-free RL.
method Introducing a Bayesian model update for based on BMC.
result Proposed - exttt{BMC} algorithm efficiently balances exploration and exploitation.
We propose a policy improvement algorithm for Reinforcement Learning (RL) which is called Rerouted Behavior Improvement (RBI). RBI is designed to take into account the evaluation errors of the Q-function. Such errors are common in RL when learning the -value from finite past experience data. Greedy policies or even …
Improved Thompson Sampling for Bayesian Optimization.
problem Handling the exploitation-exploration dilemma in Bayesian optimization.
method Incorporating epsilon-greedy policy into Thompson Sampling.
result Epsilon-greedy Thompson Sampling outperforms standard TS extremes.
Many policy gradient methods are variants of Actor-Critic (AC), where a value function (critic) is learned to facilitate updating the parameterized policy (actor). The update to the actor involves a log-likelihood update weighted by the action-values, with the addition of entropy regularization for soft variants. In th…
Real Time Dynamic Programming (RTDP) is an online algorithm based on Dynamic Programming (DP) that acts by 1-step greedy planning. Unlike DP, RTDP does not require access to the entire state space, i.e., it explicitly handles the exploration. This fact makes RTDP particularly appealing when the state space is large and…
Cramming method evaluates learned policies from contextual bandits efficiently.
problem Evaluating final learned policies from contextual bandit algorithms.
method On-policy evaluation using a single pass of data, ensuring consistency and asymptotic normality.
result Cramming method reduces evaluation standard error by approximately 40% compared to off-policy methods.
Multi-step greedy policies have been extensively used in model-based reinforcement learning (RL), both when a model of the environment is available (e.g.,~in the game of Go) and when it is learned. In this paper, we explore their benefits in model-free RL, when employed using multi-step dynamic programming algorithms: …
Bayesian sOED uses PG reinforcement learning for efficient experiment design.
problem Optimizing sequential experiments for nonlinear models with limited data.
method Formulated as POMDP, solved via PG methods with neural network parameterization.
result Demonstrated advantages over batch and greedy designs in contaminant source inversion.
New guarantees for adaptive combinatorial maximization with various objectives.
problem Maximizing under cardinality constraints and minimum cost coverage in adaptive settings.
method Bayesian approach with comprehensive approximation guarantees for various utility functions.
result Maximal gain ratio is a new parameter that provides stronger approximation guarantees than greedy policies.
This paper investigates a type of instability that is linked to the greedy policy improvement in approximated reinforcement learning. We show empirically that non-deterministic policy improvement can stabilize methods like LSPI by controlling the improvements' stochasticity. Additionally we show that a suitable represe…
Study uses PPLs to model and forecast COVID-19 spread and policy interventions.
problem Forecast and control the spread of COVID-19 using policy interventions.
method Compartmental models, probabilistic programming, inference, greedy algorithm.
result Optimal series of policy interventions can control the infected population.
We analyze the problem of learning a single user's preferences in an active learning setting, sequentially and adaptively querying the user over a finite time horizon. Learning is conducted via choice-based queries, where the user selects her preferred option among a small subset of offered alternatives. These queries …
Proposes H-UCRL for efficient model-based RL with sublinear regret.
problem Greedy policy exploration in model-based RL ignores epistemic uncertainty.
method Reparameterizes plausible models, hallucinates control, augments input space, solves with greedy planners.
result H-UCRL achieves provably sublinear regret for Gaussian Process models.
Clinician-in-the-Loop Decision Making: Reinforcement Learning with Near-Optimal Set-Valued Policiescs.LG
A new RL approach learns near-equivalent actions for healthcare decisions.
problem Finding optimal actions in healthcare settings where actions may be near-equivalent.
method Temporal difference learning with a near-greedy heuristic for action selection.
result The proposed algorithm discovers meaningful near-equivalent actions and converges well.
This work improves RLHF performance guarantees using greedy sampling.
problem Learning the KL-regularized target with preference feedback.
method General preference model, greedy sampling.
result Order-wise improvements over existing RLHF performance guarantees.
The design of multiple experiments is commonly undertaken via suboptimal strategies, such as batch (open-loop) design that omits feedback or greedy (myopic) design that does not account for future effects. This paper introduces new strategies for the optimal design of sequential experiments. First, we rigorously formul…
New RL theory predicts deep RL success based on greedy actions under random policies.
problem Current RL theory struggles to predict practical performance.
method Introduced BRIDGE dataset and effective horizon measure.
result Effective horizon correlates better with deep RL success than prior bounds.
In this paper, we consider adaptive decision-making problems for stochastic state estimation with partial observations. First, we introduce the concept of weak adaptive submodularity, a generalization of adaptive submodularity, which has found great success in solving challenging adaptive state estimation problems. The…
This paper investigates trajectory tracking problem for a class of underactuated autonomous underwater vehicles (AUVs) with unknown dynamics and constrained inputs. Different from existing policy gradient methods which employ single actor-critic but cannot realize satisfactory tracking control accuracy and stable learn…
GNMC reduces XCSF population size while preserving function approximation and policy accuracy.
problem Population bloat in XCSF compaction.
method Introduced GNMC, a novel compaction algorithm.
result GNMC reduces population size significantly without compromising function approximation or policy accuracy.
The question of how to explore, i.e., take actions with uncertain outcomes to learn about possible future rewards, is a key question in reinforcement learning (RL). Here, we show a surprising result: We show that Q-learning with nonlinear Q-function and no explicit exploration (i.e., a purely greedy policy) can learn s…
New method learns decisions from collective preferences without individual covariates.
problem Making decisions online without individual covariates.
method Collaborative filtering, matrix completion bandit, ε-greedy policy, online gradient descent, inverse propensity weighting.
result Method outperforms benchmarks and reveals new discoveries.
Simplifies RL training with fewer techniques, reducing bias and instability.
problem Training instabilities and high sample complexity in RL.
method Introduced a simple deterministic policy gradient, used propensity estimation, and delayed policy updates.
result Improved performance and reduced sample complexity through these techniques.
The famous Policy Iteration algorithm alternates between policy improvement and policy evaluation. Implementations of this algorithm with several variants of the latter evaluation stage, e.g, -step and trace-based returns, have been analyzed in previous works. However, the case of multiple-step lookahead policy impr…
State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing \emph{full-planning} on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon…
Study improves CTS's approximation regret for combinatorial bandits.
problem Improving CTS's performance on non-exact oracles.
method Develops a new upper bound for CTS under specific conditions.
result First approximation regret upper bound for CTS.
SymCircuit learns PC structure via entropy-regularized RL, improving inference efficiency and accuracy.
problem Greedy algorithms in PC structure learning lead to suboptimal solutions.
method Entropy-regularized reinforcement learning to train a learned generative policy for PC structure inference.
result SymCircuit learns the optimal policy as a tempered Bayesian posterior, improving inference efficiency and accuracy.
New algorithm for reinforcement learning reduces complexity and guarantees convergence.
problem Reinforcement learning problems with convex occupancy measures.
method MD-CURL, inspired by mirror descent, uses non-standard regularization.
result Achieves convergence guarantees and simple closed-form solution.
GPE algorithm optimizes nonparametric contextual bandits with efficient regret bounds.
problem Optimizing nonparametric contextual bandits with efficient regret bounds.
method Inspired by Policy Elimination, GPE uses oracle-efficient techniques for nonparametric classes with infinite VC-dimension.
result GPE is regret-optimal for policy classes with integrable entropy, and for larger entropy, it provides an -greedy algorithm with matching regret bounds.