ASE safely explores unknown MDPs with unknown dynamics, improving sample efficiency.
problem Balancing exploration and safety in unknown MDPs with stochastic dynamics.
method Exploits analogies between state-action pairs to safely learn near-optimal policies.
result Empirically improves sample efficiency compared to existing methods.
New algorithm reduces dynamic regret for MDPs with unknown transition and adversarial rewards.
problem Episodic linear mixture MDPs with unknown transition and adversarial rewards.
method Combines occupancy-measure-based global optimization and policy-based variance-aware value-targeted regression.
result Achieves near-optimal dynamic regret of O ~ ( d H 3 K + H K ( H + P ˉ K ) ) \widetilde{\mathcal{O}}(d \sqrt{H^3 K} + \sqrt{HK(H + \bar{P}_K)}) O ( d H 3 K + H K ( H + P ˉ K ) ) . Efficient RL for linear MDPs with unknown transitions.
problem Long planning horizons and unknown state transitions in linear mixture MDPs.
method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.
result Achieves optimal regret up to logarithmic factors.
New algorithm reduces reinforcement learning regret for linear MDPs with unknown transitions.
problem Adversarial linear mixture MDPs with bandit feedback and unknown transition.
method Proposes a new algorithm with a least square estimator and self-normalized concentration.
result Achieves improved regret bound with high probability.
RL approach for target tracking with unknown dynamics and sensor control.
problem Tracking an unknown target with sensor control.
method Track-MDP formulation for RL, compared with POMDP.
result Optimal RL policy tracks all target paths with certainty.
Efficient algorithm for learning MDPs with unknown transitions and bandit feedback.
problem Learning in episodic finite-horizon MDPs with unknown transitions and bandit feedback.
method Proposes an efficient algorithm with i l d e O ( L ∣ X ∣ ∣ A ∣ T ) \mathcal{ ilde{O}}(L|X|\sqrt{|A|T}) i l d e O ( L ∣ X ∣ ∣ A ∣ T ) regret. result Achieves i l d e O ( T ) \mathcal{ ilde{O}}(\sqrt{T}) i l d e O ( T ) regret, matching previous work with full-information feedback. We introduce and analyse two algorithms for exploration-exploitation in discrete and continuous Markov Decision Processes (MDPs) based on exploration bonuses. SCAL + ^+ + is a variant of SCAL (Fruit et al., 2018) that performs efficient exploration-exploitation in any unknown weakly-communicating MDP for which an upper bo…
Algorithm POLO learns low-rank MDPs with adversarial changes in full-info feedback.
problem Learning low-rank MDPs with adversarial changes and unknown transition probabilities.
method Policy optimization-based algorithm POLO with regret guarantee.
result POLO achieves sublinear regret guarantee with no dependence on state space size.
Develops robust MDPs for unknown disturbances with performance guarantees.
problem Unknown disturbance distribution in MDPs.
method Empirical distribution, sublevel set of distance function, weak convergence, concentration inequality.
result Robust optimal value function converges to true optimal value function with increasing sample sizes.
In classical reinforcement learning, when exploring an environment, agents accept arbitrary short term loss for long term gain. This is infeasible for safety critical applications, such as robotics, where even a single unsafe action may cause system failure. In this paper, we address the problem of safely exploring fin…
New algorithm handles MDPs with unknown, changing rewards efficiently.
problem Handling MDPs with unknown, changing rewards in large state spaces.
method Developed an algorithm with O ( τ ( ln ∣ S ∣ + ln ∣ A ∣ ) T ln ( T ) ) O(\sqrt{τ(\ln|S|+\ln|A|)T}\ln(T)) O ( τ ( ln ∣ S ∣ + ln ∣ A ∣ ) T ln ( T )) regret bound and a modified algorithm with polynomial complexity. result Achieved state-of-the-art regret bounds for large scale MDPs with changing rewards.
Improved FPL algorithms for adversarial MDPs with better regret bounds.
problem Adversarial rewards and unknown transitions in MDPs.
method Refined analysis of FPL algorithms, matching current best regret bounds.
result Improved regret bounds for FPL algorithms in adversarial MDPs.
Paper compares UCB policy to new adaptive RL methods.
problem Optimal adaptive policies for Markovian decision processes with unknown transition probabilities.
method Compared UCB policy with MDP-Deterministic Minimum Empirical Divergence and Posterior sampling methods.
result MDP-DMED outperforms UCB in the tested RL scenarios.
Algorithm optimizes decision-making in unknown MDPs with minimal regret.
problem Optimizing decision-making in unknown discrete MDPs with bounded expected shortest path.
method Developed BUCRL{} algorithm achieving i l d e O ( D S A T ) ilde{\mathcal{O}}(\sqrt{DSAT}) i l d e O ( D S A T ) regret. result First polynomial time Bayesian algorithm for unknown MDPs with high probability worst-case regret.
New RL approach learns dynamic VCG mechanisms in unknown MDP environments.
problem Learning dynamic VCG mechanisms in unknown MDP environments.
method Reward-free online RL for exploration, combined with function approximation.
result Regret bound of O ~ ( T 2 / 3 ) \tilde{\mathcal{O}}(T^{2/3}) O ~ ( T 2/3 ) for dynamic VCG mechanism learning. Improved regret bound for online learning in unknown MDPs.
problem Online learning in unknown episodic MDPs with changing loss functions.
method Adapts adversarial MDP model to convex performance criteria using entropic regularization.
result Achieved i l d e O ( L ∣ X ∣ ∣ A ∣ T ) ilde{O}(L|X|\sqrt{|A|T}) i l d e O ( L ∣ X ∣ ∣ A ∣ T ) regret bound. UCRL-V algorithm achieves optimal regret in unknown MDPs.
problem Optimizing reinforcement learning in unknown finite Markov decision processes.
method Empirical Bernstein inequalities for variance-based confidence intervals.
result Achieves optimal regret i l d e O ( D S A T ) ilde{\mathcal{O}}(\sqrt{DSAT}) i l d e O ( D S A T ) up to logarithmic factors. The paper establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
problem Learning Latent Markov Decision Processes (LMDPs) with separated components.
method The paper considers various notions of separation and establishes a nearly-sharp statistical threshold for efficient learning. It also presents a quasi-polynomial algorithm with time complexity scaling in terms of the statistical threshold under a weaker assumption of separability under the optimal policy, and a near-matching time complexity lower bound under the exponential time hypothesis.
result Establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
New model-free algorithms learn representations for low-rank MDPs efficiently.
problem Learning representations in reinforcement learning for low-rank MDPs.
method Developed minimax representation learning objective and interleaved with reward-free exploration.
result Proven sample efficiency and scalability to complex environments.
Paper explores state-action equivalence in RL, improving regret bounds.
problem Improving reinforcement learning performance by leveraging state-action equivalence.
method Introduces a notion of similarity between state-action pairs, defines equivalence structure, and presents algorithms for confidence sets.
result Confidence sets improve RL performance, especially in known equivalence structures.
New algorithm achieves data-dependent regret bounds in MDPs with unknown transitions.
problem Achieving best-of-both-worlds guarantees with data-dependent regret bounds in MDPs with unknown transitions.
method Optimistic follow-the-regularized-leader algorithm with new optimistic Q-function estimators and transition bonus.
result First-order, second-order, and path-length bounds with polylog(T) regret in the stochastic regime.
Paper optimizes learning MDPs with adversarial rewards using linear models.
problem Learning MDPs with adversarial rewards and changing reward functions.
method Proposes POWERS, an optimistic policy optimization algorithm.
result Achieves nearly optimal regret bound of O ( d H T ) O(dH\sqrt{T}) O ( d H T ) . Inverse Reinforcement Learning (IRL) describes the problem of learning an unknown reward function of a Markov Decision Process (MDP) from observed behavior of an agent. Since the agent's behavior originates in its policy and MDP policies depend on both the stochastic system dynamics as well as the reward function, the …
New RL algorithm tackles online robust MDPs with uncertainty.
problem Developing robust reinforcement learning models for real-world environments.
method Proposes a robust optimistic policy optimization algorithm for online robust MDPs.
result Establishes the first regret bound for online robust MDPs.
Efficiently computes indices for UCB and DMED algorithms in reinforcement learning.
problem Efficiently compute indices for UCB and DMED algorithms in reinforcement learning.
method Developed efficient methods to compute indices for UCB and DMED algorithms by solving systems of equations.
result Significant computational time savings and improved regret performance demonstrated.
DARLING tackles non-stationary RL with guarantees, improving dynamic regret.
problem Non-stationary reinforcement learning in unknown change points.
method Detection Augmented Reinforcement Learning (DARLING) for tabular and linear MDPs.
result DARLING matches minimax lower bounds in tabular and linear MDPs.
Improved regret bounds for inventory management with unknown demand distribution.
problem Stochastic inventory control problem with censored demands and positive lead times.
method Utilized convexity properties and derived bias bounds to connect to stochastic convex bandit optimization.
result Regret bound of i l d e O ( L T + D ) ilde{O}(L\sqrt{T}+D) i l d e O ( L T + D ) for the inventory control problem. FLAMBE tackles RL in low rank MDPs by learning features.
problem Dealing with the curse of dimensionality in RL.
method Develops FLAMBE, a method that engages in exploration and representation learning for RL in low rank transition models.
result FLAMBE efficiently learns features for RL in low rank transition models.
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound c c c on the span of the optimal bias function is known. For an MDP with S S S states, A A A actions and Γ ≤ S Γ\leq S Γ ≤ S possible next states, we prove a …
New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.
problem Nonstationary reinforcement learning with evolving reward and state transition functions.
method Developed a new algorithm LSVI-UCB-Restart with periodic restart, and parameter-free Ada-LSVI-UCB-Restart for unknown variation budgets.
result First minimax dynamic regret lower bound for nonstationary linear MDPs and linear MDPs lower bound.
Paper improves sample complexity for reward-free RL in low-rank MDPs.
problem Reward-free RL in low-rank MDPs with unknown representation and weights.
method Proposes a novel model-based algorithm RAFFLE with improved sample complexity.
result RAFFLE achieves ε ε ε -optimal policy and accurate system identification with significantly fewer samples. New algorithm optimizes exploration in unknown MDPs.
problem Optimal exploration in unknown Markov decision processes.
method Trajectory-optimization-based approximate solution using Bayesian experimental design.
result Empirically superior to intrinsic-motivation-based algorithms in convergence and model fidelity.
Paper uses RL to synthesize control policies for LTL objectives in uncertain environments.
problem Control policies for uncertain, probabilistic environments with temporal logic specifications.
method Model-free RL algorithm, LTL to LDBA translation, synchronous reward function, asymptotic satisfaction probability.
result RL algorithm maximizes satisfaction probability of LTL objectives in PL-MDPs.
Logarithmic regret for continuous-time reinforcement learning.
problem Continuous-time Markov decision processes with unknown transition probabilities and holding times.
method Upper confidence reinforcement learning, mean holding time estimation, stochastic comparison of point processes.
result Logarithmic regret bound achieved in finite time.
Adversarial online multi-task RL with task separation.
problem Minimize regret in an adversarial online multi-task setting with unknown MDPs.
method Prove minimax and instance-specific lower bounds, develop a clustering algorithm with optimal sample complexity and regret.
result Tight sample complexity and regret bounds for adversarial online multi-task RL.
New algorithm reduces regret for linear bandits with unknown noise variance.
problem Finding optimal actions in linear bandits with varying noise variance.
method Adaptive algorithm with Freedman-type concentration inequality and multi-layer structure.
result Achieves i l d e O ( d ∑ k = 1 K σ k 2 + d ) ilde{O}(d \sqrt{\sum_{k = 1}^K σ_k^2} + d) i l d e O ( d ∑ k = 1 K σ k 2 + d ) regret for linear bandits. Efficient RL algorithm for multinomial logistic MDPs with provable guarantees.
problem Model-based RL for episodic MDPs with unknown transition probabilities.
method Upper confidence bound-based algorithm for exploration-exploitation balance.
result Achieves i l d e O ( d H 3 T ) ilde{O}(d \sqrt{H^3 T}) i l d e O ( d H 3 T ) regret bound for multinomial logistic models. Algorithm learns from offline data to improve performance in target environment.
problem Learning from offline data in a target environment with unknown shifts.
method Adaptive algorithm that uses offline data to improve performance when informative.
result Algorithm provably improves performance over purely online learning when offline data are informative.
The problem of reinforcement learning in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion is considered, when the learner interacts with the system in a single stream of observations, starting from an initial state without any reset. We revisit the minimax lower bound for that pr…
New model selects robustly in adversarial reinforcement learning with unknown corruption.
problem Adversarial corruption in reinforcement learning with unknown total corruption amount.
method Model selection approach for finite-horizon tabular and linear MDPs.
result First worst-case optimal bound without knowledge of total corruption.
Paper proposes a method for learning and planning in time-varying environments.
problem Learning and planning in unknown, time-varying environments.
method Computes the maximally likely model of the environment using maximum likelihood estimation.
result Generalizes learning algorithms for time-invariant Markov decision processes to time-varying ones.
We introduce the active exploration problem in Markov decision processes (MDPs). Each state of the MDP is characterized by a random value and the learner should gather samples to estimate the mean value of each state as accurately as possible. Similarly to active exploration in multi-armed bandit (MAB), states may have…
Study reward-free RL in non-linear settings, improving efficiency and removing assumptions.
problem Improving sample efficiency in reward-free reinforcement learning for non-linear function approximation.
method Proposed RFOLIVE algorithm for minimal structural assumptions, analyzed hardness results for reward-free and reward-aware exploration.
result Statistical efficiency and hardness results under various structural assumptions, no need for reachability or explorability assumptions.
Efficiently selects seed nodes to maximize content influence in unknown social networks.
problem Maximizing content spread in social networks with unknown network model.
method Formulated as an infinite-horizon discounted MDP, uses model-based reinforcement learning to select seed users adaptively.
result Established a regret bound of O ~ ( T ) \widetilde O(\sqrt{T}) O ( T ) for the algorithm. New algorithm reduces suboptimality in imitation learning to nearly optimal levels.
problem Statistical limits of imitation learning in MDPs with known transitions.
method Mimic-MD algorithm and reduction to value estimation problem.
result Upper bound of O ( ∣ S ∣ H 3 / 2 / N ) O(|\mathcal{S}|H^{3/2}/N) O ( ∣ S ∣ H 3/2 / N ) for suboptimality, with efficient computation. Hybrid RL algorithms improve offline and online RL in linear MDPs.
problem Improving RL performance without single-policy concentrability.
method Developed computationally efficient algorithms for PAC and regret-minimizing RL in linear MDPs.
result Achieved sharper error or regret bounds for linear MDPs.
New bounds for learning near-optimal policies in CMDPs with constraints.
problem Optimizing policies in CMDPs with constraints.
method Model-based algorithm addressing relaxed and strict feasibility.
result Near-optimal sample complexity bounds for CMDPs.
Bayesian regularization improves policy performance in noisy MDPs.
problem Suboptimal policies from estimated model parameters.
method Bayesian regularization of MDP objective function with prior information.
result Regularized policies show better robustness against model noise.