Designing a safe policy for uncertain environments is crucial in real-world control systems. However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework. This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP), where an optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments. We first prove that the conventional policy gradient approach to the Lagrangian max-min formulation can become trapped in suboptimal solutions. This occurs when its inner minimization encounters a sum of conflicting gradients from the objective and constraint functions. To address this, we leverage the epigraph form of the RCMDP problem, which resolves the conflict by selecting a single gradient from either the objective or the constraints. Building on the epigraph form, we propose a bisection search algorithm with a policy gradient subroutine and prove that it identifies an $\varepsilon$-optimal policy in an RCMDP with $\widetilde{\mathcal{O}}(\varepsilon^{-4})$ robust policy evaluations.

We study the reinforcement learning (RL) problem in a constrained Markov decision process (CMDP), where an agent explores the environment to maximize the expected cumulative reward while satisfying a single constraint on the expected total utility value in every episode. While this problem is well understood in the tabular setting, theoretical results for function approximation remain scarce. This paper closes the gap by proposing an RL algorithm for linear CMDPs that achieves $\widetilde{\mathcal{O}}(\sqrt{K})$ regret with an episode-wise zero-violation guarantee. Furthermore, our method is computationally efficient, scaling polynomially with problem-dependent parameters while remaining independent of the state space size. Our results significantly improve upon recent linear CMDP algorithms, which either violate the constraint or incur exponential computational costs.

Neural networks play a central role in the construction of learning models for artificial intelligence and machine learning. This is because neural networks are highly flexible and can approximate a wide variety of maps with high accuracy. The flexibility of neural networks is theoretically guaranteed by using universal approximation theorems. When the input and output spaces have finite dimensions, the universal approximation property of neural networks has been intensively investigated under various conditions of width, depth, and activation functions. However, these finite-dimensional results cannot be directly applied to settings in which an input or output space has infinite dimensions, such as functional data analysis and neural processes. This study provides a universal approximation theorem with neural networks for uniformly continuous maps between function spaces, whose dimensions can be infinite.

Various data exhibit symmetry, including permutations in graphs and point clouds. Machine learning methods that utilize this symmetry have achieved considerable success. In this study, we explore learning models for data exhibiting group symmetry. Our focus is on transforming deep neural networks using Reynolds operators, which average over the group to convert a function into an invariant or equivariant form. While learning methods based on Reynolds operators are well-established, they often face computational complexity challenges. To address this, we introduce two new methods that reduce the computational burden associated with the Reynolds operator: (i) Although the Reynolds operator traditionally averages over the entire group, we demonstrate that it can be effectively approximated by averaging over specific subsets of the group, termed the Reynolds design. (ii) We reveal that the pre-model does not require all input variables. Instead, using a select number of partial inputs (Reynolds dimension) is sufficient to achieve a universally applicable model. Employing these methods, which hinge on the Reynolds design and Reynolds dimension concepts, allows us to construct universally applicable models with manageable computational complexity. Our experiments on benchmark data indicate that our approach is more efficient than existing methods.

Mirror descent value iteration (MDVI), an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL), has served as the basis for recent high-performing practical RL algorithms. However, despite the use of function approximation in practice, the theoretical understanding of MDVI has been limited to tabular Markov decision processes (MDPs). We study MDVI with linear function approximation through its sample complexity required to identify an $\varepsilon$-optimal policy with probability $1-\delta$ under the settings of an infinite-horizon linear MDP, generative model, and G-optimal design. We demonstrate that least-squares regression weighted by the variance of an estimated optimal value function of the next state is crucial to achieving minimax optimality. Based on this observation, we present Variance-Weighted Least-Squares MDVI (VWLS-MDVI), the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs. Furthermore, we propose a practical VWLS algorithm for value-based deep RL, Deep Variance Weighting (DVW). Our experiments demonstrate that DVW improves the performance of popular value-based deep RL algorithms on a set of MinAtar benchmarks.

Markov chain Monte Carlo (MCMC), such as Langevin dynamics, is valid for approximating intractable distributions. However, its usage is limited in the context of deep latent variable models owing to costly datapoint-wise sampling iterations and slow convergence. This paper proposes the amortized Langevin dynamics (ALD), wherein datapoint-wise MCMC iterations are entirely replaced with updates of an encoder that maps observations into latent variables. This amortization enables efficient posterior sampling without datapoint-wise iterations. Despite its efficiency, we prove that ALD is valid as an MCMC algorithm, whose Markov chain has the target posterior as a stationary distribution under mild assumptions. Based on the ALD, we also present a new deep latent variable model named the Langevin autoencoder (LAE). Interestingly, the LAE can be implemented by slightly modifying the traditional autoencoder. Using multiple synthetic datasets, we first validate that ALD can properly obtain samples from target posteriors. We also evaluate the LAE on the image generation task, and show that our LAE can outperform existing methods based on variational inference, such as the variational autoencoder, and other MCMC-based methods in terms of the test likelihood.

Uncertainty evaluation is a core technique when deep neural networks (DNNs) are used in real-world problems. In practical applications, we often encounter unexpected samples that have not seen in the training process. Not only achieving the high-prediction accuracy but also detecting uncertain data is significant for safety-critical systems. In statistics and machine learning, Bayesian inference has been exploited for uncertainty evaluation. The Bayesian neural networks (BNNs) have recently attracted considerable attention in this context, as the DNN trained using dropout is interpreted as a Bayesian method. Based on this interpretation, several methods to calculate the Bayes predictive distribution for DNNs have been developed. Though the Monte-Carlo method called MC dropout is a popular method for uncertainty evaluation, it requires a number of repeated feed-forward calculations of DNNs with randomly sampled weight parameters. To overcome the computational issue, we propose a sampling-free method to evaluate uncertainty. Our method converts a neural network trained using dropout to the corresponding Bayesian neural network with variance propagation. Our method is available not only to feed-forward NNs but also to recurrent NNs such as LSTM. We report the computational efficiency and statistical reliability of our method in numerical experiments of language modeling using RNNs, and the out-of-distribution detection with DNNs.

In this study, we consider a transfer-learning problem using the parameter transfer approach, in which a suitable parameter of feature mapping is learned through one task and applied to another objective task. We introduce the notion of local stability and parameter transfer learnability of parametric feature mapping, and derive an excess risk bound for parameter transfer algorithms. As an application of parameter transfer learning, we discuss the performance of sparse coding in self-taught learning. Although self-taught learning algorithms with a large volume of unlabeled data often show excellent empirical performance, their theoretical analysis has not yet been studied. In this paper, we also provide a theoretical excess risk bound for self-taught learning. In addition, we show that the results of numerical experiments agree with our theoretical analysis.

In this letter, we propose a variable selection method for general nonparametric kernel-based estimation. The proposed method consists of two-stage estimation: (1) construct a consistent estimator of the target function, and (2) approximate the estimator using a few variables by [Formula: see text]-type penalized estimation. We see that the proposed method can be applied to various kernel nonparametric estimation such as kernel ridge regression, kernel-based density, and density-ratio estimation. We prove that the proposed method has the property of variable selection consistency when the power series kernel is used. Here, the power series kernel is a certain class of kernels containing polynomial and exponential kernels. This result is regarded as an extension of the variable selection consistency for the nonnegative garrote (NNG), a special case of the adaptive Lasso, to the kernel-based estimators. Several experiments, including simulation studies and real data applications, show the effectiveness of the proposed method.

In the theory of convex optimization, the derivative of the objective function including the gradient and the Hessian is typically used to search the optimum point. However, in real-world applications, it may be that the concrete form of the function is unknown or the computation of the derivative is difficult, and thus, the derivative of the objective function is unavailable. To solve the problem, optimization methods without the derivative have been developed in recent years. Such methods are called bandit optimization methods in the machine learning community. In this paper, we introduce basic bandit optimization algorithms and explain their performance.

Metaheuristics are required in invariance when transforming the solution space or objective function (transformation invariance) for the robustness of the optimization algorithm because they are used in various environments. In this study, we first construct an analysis framework based on transformation invariance using a proof. Second, we point out that particle swarm optimization (PSO) lacks invariance under rotation of the solution space (rotational invariance) using the analysis framework. Third, we develop PSO with rotational invariance using correlativity (CRIPSO), which has a coordinate transformation function based on a covariance matrix. Fourth, we confirm that CRIPSO shows rotational invariance using the analysis framework. Finally, the performance of CRIPSO is verified through numerical experiments for typical separable benchmark functions with and without rotation of the solution space by comparing PSO values.

In the above titled paper[2],Fig. 1andFig. 4are based on incorrect numerical calculation. The correct plots of[2, Fig. 1]are given in[1, Fig. 3]as follows.

In the captioned paper[3],Fig. 3andFig. 4are based on incorrect numerical calculation. The corrected plots in[3, Fig. 3]look as follows:

The dueling bandit is a learning framework where the feedback information in the learning process is restricted to noisy comparison between a pair of actions. In this paper, we address a dueling bandit problem based on a cost function over a continuous space. We propose a stochastic mirror descent algorithm and show that the algorithm achieves an $O(\sqrt{T\log T})$-regret bound under strong convexity and smoothness assumptions for the cost function. Then, we clarify the equivalence between regret minimization in dueling bandit and convex optimization for the cost function. Moreover, considering a lower bound in convex optimization, it is turned out that our algorithm achieves the optimal convergence rate in convex optimization and the optimal regret in dueling bandit except for a logarithmic factor.

We discuss the asymptotic behavior of conversions between two independent and identical distributions up to the second-order conversion rate when the conversion is produced by a deterministic function from the input probability space to the output probability space. To derive the second-order conversion rate, we introduce new probability distributions named Rayleigh-normal distributions. The family of Rayleigh-normal distributions includes a Rayleigh distribution and coincides with the standard normal distribution in the limit case. Using this family of probability distributions, we represent the asymptotic second-order rates for the distribution conversion. As an application, we also consider the asymptotic behavior of conversions between the multiple copies of two pure entangled states in quantum systems when only local operations and classical communications (LOCC) are allowed. This problem contains entanglement concentration, entanglement dilution, and a kind of cloning problem with LOCC restriction as special cases.

We consider random number conversion (RNC) through random number storage with restricted size. We clarify the relation between the performance of RNC and the size of storage in the framework of the first- and second-order asymptotics, and derive their rate regions. Then, we show that the results for RNC with restricted storage recover those for conventional RNC without storage in the limit of storage size. To treat RNC via restricted storage, we introduce a new kind of probability distributions named generalized Rayleigh-normal distributions. Using the generalized Rayleigh-normal distributions, we can describe the second-order asymptotic behavior of RNC via restricted storage in a unified manner. As an application to quantum information theory, we analyze LOCC conversion via entanglement storage with restricted size. Moreover, we derive the optimal LOCC compression rate under a constraint of conversion accuracy.

We consider a transfer-learning problem by using the parameter transfer approach, where a suitable parameter of feature mapping is learned through one task and applied to another objective task. Then, we introduce the notion of the local stability of parametric feature mapping and parameter transfer learnability, and thereby derive a learning bound for parameter transfer algorithms. As an application of parameter transfer learning, we discuss the performance of sparse coding in self-taught learning. Although self-taught learning algorithms with plentiful unlabeled data often show excellent empirical performance, their theoretical analysis has not been studied. In this paper, we also provide the first theoretical learning bound for self-taught learning.

In this paper, we focus on Cuckoo Search (CS) that is one of metaheuristics, and propose an adaptive CS to improve its search performance and usability. First, we analyze basically and qualitatively the effects of CS's parameter on its search dynamics. Second, from the analysis results, we define an indicator that evaluates the search state of CS based on the effective metaheuristics strategy. Moreover, based on the indicator, we construct a new mechanism to control the search state by adaptively adjusting a parameter of CS. The performance of the proposed adaptive CS with the parameter adjustment mechanism is verified through numerical simulations for several types of typical benchmark problems.

Recently, two of the authors showed that entanglement concentration is irreversible. However, it is still not clear what kind of LOCC conversion is reversible. We derive the necessary and sufficient condition for reversibility of LOCC conversion between two bipartite pure entangled states in an asymptotic setting. Simultaneously, we evaluate how many copies of the initial state is to be lost to overcome irreversibility of LOCC conversion. Our result is useful for designing how to store entangled states via LOCC operations without error.

We consider random number conversion through random number storage with restricted size. We clarify the relation between the performance of RNC and the size of storage in the framework of first- and second-order asymptotics, and derive their rate regions.

We treat a random number generation from an i.i.d. probability distribution of P to that of Q. When Q or P is a uniform distribution, the problems have been well-known as the uniform random number generation and the resolvability problem respectively, and analyzed not only in the context of the first order asymptotic theory but also that in the second asymptotic theory. On the other hand, when both P and Q are not a uniform distribution, the second order asymptotics has not been treated. In this paper, we focus on the second order asymptotics of random number generation for arbitrary probability distributions P and Q on a finite set. In particular, we derive the optimal second order generation rate under an arbitrary permissible confidence coefficient.