Projected Inverse Dynamics Control (PIDC) is commonly used in robots subject to contact, especially in quadrupedal systems. Many methods based on such dynamics have been developed for quadrupedal locomotion tasks, and only a few works studied simple interactions between the robot and environment, such as pressing an E-stop button. To facilitate the interaction requiring exact force control for safety, we propose a novel interaction force control scheme for underactuated quadrupedal systems relying on projection techniques and Quadratic Programming (QP). This algorithm allows the robot to apply a desired interaction force to the environment without using force sensors while satisfying physical constraints and inducing minimal base motion. Unlike previous projection-based methods, the QP design uses two selection matrices in its hierarchical structure, facilitating the decoupling between force and motion control. The proposed algorithm is verified with a quadrupedal robot in a high-fidelity simulator. Compared to the QP designs without the strategy of using two selection matrices and the PIDC method for contact force control, our method provided more accurate contact force tracking performance with minimal base movement, paving the way to approach the exact interaction force control for underactuated quadrupedal systems.

In sponsored search advertising (SSA), advertisers need to select keywords and determine matching types for selected keywords simultaneously, i.e., keyword targeting. An optimal keyword targeting strategy guarantees reaching the right population effectively. This paper aims to address the keyword targeting problem, which is a challenging task because of the incomplete information of historical advertising performance indices and the high uncertainty in SSA environments. First, we construct a data distribution estimation model and apply a Markov Chain Monte Carlo method to make inference about unobserved indices (i.e., impression and click-through rate) over three keyword matching types (i.e., broad, phrase and exact). Second, we formulate a stochastic keyword targeting model (BB-KSM) combining operations of keyword selection and keyword matching to maximize the expected profit under the chance constraint of the budget, and develop a branch-and-bound algorithm incorporating a stochastic simulation process for our keyword targeting model. Finally, based on a realworld dataset collected from field reports and logs of past SSA campaigns, computational experiments are conducted to evaluate the performance of our keyword targeting strategy. Experimental results show that, (a) BB-KSM outperforms seven baselines in terms of profit; (b) BB-KSM shows its superiority as the budget increases, especially in situations with more keywords and keyword combinations; (c) the proposed data distribution estimation approach can effectively address the problem of incomplete performance indices over the three matching types and in turn significantly promotes the performance of keyword targeting decisions. This research makes important contributions to the SSA literature and the results offer critical insights into keyword management for SSA advertisers.

We present consistent algorithms for multiclass learning with complex performance metrics and constraints, where the objective and constraints are defined by arbitrary functions of the confusion matrix. This setting includes many common performance metrics such as the multiclass G-mean and micro F1-measure, and constraints such as those on the classifier's precision and recall and more recent measures of fairness discrepancy. We give a general framework for designing consistent algorithms for such complex design goals by viewing the learning problem as an optimization problem over the set of feasible confusion matrices. We provide multiple instantiations of our framework under different assumptions on the performance metrics and constraints, and in each case show rates of convergence to the optimal (feasible) classifier (and thus asymptotic consistency). Experiments on a variety of multiclass classification tasks and fairness-constrained problems show that our algorithms compare favorably to the state-of-the-art baselines.

In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for solving this problem either suffer from sub-optimal sample complexities or need a huge batch size. To address these limitations, we propose a Stochastic Multi-level Variance Reduction method (SMVR), which achieves the optimal sample complexity of $\mathcal{O}\left(1 / \epsilon^{3}\right)$ to find an $\epsilon$-stationary point for non-convex objectives. Furthermore, when the objective function satisfies the convexity or Polyak-{\L}ojasiewicz (PL) condition, we propose a stage-wise variant of SMVR and improve the sample complexity to $\mathcal{O}\left(1 / \epsilon^{2}\right)$ for convex functions or $\mathcal{O}\left(1 /\left(\mu\epsilon\right)\right)$ for non-convex functions satisfying the $\mu$-PL condition. The latter result implies the same complexity for $\mu$-strongly convex functions. To make use of adaptive learning rates, we also develop Adaptive SMVR, which achieves the same complexities but converges faster in practice. All our complexities match the lower bounds not only in terms of $\epsilon$ but also in terms of $\mu$ (for PL or strongly convex functions), without using a large batch size in each iteration.

A contemporary feed application usually provides blended results of organic items and sponsored items~(ads) to users. Conventionally, ads are exposed at fixed positions. Such a static exposure strategy is inefficient due to ignoring users' personalized preferences towards ads. To this end, adaptive ad exposure has become an appealing strategy to boost the overall performance of the feed. However, existing approaches to implementing the adaptive ad exposure still suffer from several limitations: 1) they usually fall into sub-optimal solutions because of only focusing on request-level optimization without consideration of the long-term application-level performance and constraints, 2) they neglect the necessity of keeping the game-theoretical properties of ad auctions, which may lead to anarchy in bidding, and 3) they can hardly be deployed in large-scale applications due to high computational complexity. In this paper, we focus on long-term performance optimization under hierarchical constraints in feeds and formulate the adaptive ad exposure as a Dynamic Knapsack Problem. We propose an effective approach: Hierarchically Constrained Adaptive Ad Exposure~(HCA2E). We present that HCA2E possesses desired game-theoretical properties, computational efficiency, and performance robustness. Comprehensive offline and online experiments on a leading e-commerce application demonstrate the significant performance superiority of HCA2E over representative baselines. HCA2E has also been deployed on this application to serve millions of daily users.

In general, H is a structured matrix defined in such a way that the product Hu corresponds to a convolution between the image u and a given kernel h representing the Point Spread Function (PSF) of the imaging system employed to measure the data. The deblurring (or deconvolution) problem consists in finding an approximation of g, given the blurred image f and, possibly, some information on the system PSF. If the blurring kernel h, underlying the matrix H, is completely unknown and it has to be inferred together with g, the resulting problem is a blind deconvolution one [32]. Since the PSF h usually represents a low-pass filter, the matrix H is, at best, very ill conditioned and directly solving the inverse problem Hu = f, even when it is feasible, leads to unmeaningful solutions. On the other side, the variational approach consists in designing and solving an optimization problem whose solutions are a good approximation of the unknown image g. In general, a variational model is the set composed by the objective function, i.e., the function to be minimized, and the possible constraints. In the variational models arising in image restoration applications, the objective function, called also energy functional, encompasses different kinds of information: the nature of the noise introduced in the acquisition process, geometrical and/or analytical properties on the image content and physical constraints on the pixel values. Usually, in all image reconstruction problems, and more generally inverse problems, the energy functional, besides the data, depends on a set of parameters; they may simply reduce to tuning parameters balancing the relative weights of the different terms in the functional but can also represent more complicate structures of the functionals themselves.

Min-max optimization problems involving nonconvex-nonconcave objectives have found important applications in adversarial training and other multi-agent learning settings. Yet, no known gradient descent-based method is guaranteed to converge to (even local notions of) min-max equilibrium in the nonconvex-nonconcave setting. For all known methods, there exist relatively simple objectives for which they cycle or exhibit other undesirable behavior different from converging to a point, let alone to some game-theoretically meaningful one~\cite{flokas2019poincare,hsieh2021limits}. The only known convergence guarantees hold under the strong assumption that the initialization is very close to a local min-max equilibrium~\cite{wang2019solving}. Moreover, the afore-described challenges are not just theoretical curiosities. All known methods are unstable in practice, even in simple settings. We propose the first method that is guaranteed to converge to a local min-max equilibrium for smooth nonconvex-nonconcave objectives. Our method is second-order and provably escapes limit cycles as long as it is initialized at an easy-to-find initial point. Both the definition of our method and its convergence analysis are motivated by the topological nature of the problem. In particular, our method is not designed to decrease some potential function, such as the distance of its iterate from the set of local min-max equilibria or the projected gradient of the objective, but is designed to satisfy a topological property that guarantees the avoidance of cycles and implies its convergence.

We study policy optimization for Markov decision processes (MDPs) with multiple reward value functions, which are to be jointly optimized according to given criteria such as proportional fairness (smooth concave scalarization), hard constraints (constrained MDP), and max-min trade-off. We propose an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $\tilde{O}(1/T)$ global convergence with exact gradients. Empirically, the ARNPG-guided algorithms also demonstrate superior performance compared to some existing policy gradient-based approaches in both exact gradients and sample-based scenarios.

This paper presents a sample-efficient data-driven method to design model predictive control (MPC) for cable-actuated soft robotics using Bayesian optimization. Instead of modeling the complex dynamics of the soft robots, the proposed approach uses Bayesian optimization to search the best-guessed low-dimensional prediction model and its associated controller to minimize the objective function of closed-loop responses. The prediction model is updated by Bayesian optimization from the closed-loop input-output data in each iteration. A linear MPC is then designed based on the updated prediction model, and evaluated based on the closed-loop responses. Different from directly searching controller parameters, the closed-loop system stability, and inputs/outputs constraints can be easily handled in the MPC design. After a few iterations, a convergent solution of a (sub-)optimal controller can be obtained, which minimizes the user-defined closed-loop performance index. The proposed method is simulated and validated by a high-fidelity simulation of a cable-actuated soft robot. The simulation results demonstrate that the proposed approach can achieve desired tracking controller for the soft robot without a prior-known model.

In this paper, we leverage the rapid advances in imitation learning, a topic of intense recent focus in the Reinforcement Learning (RL) literature, to develop new sample complexity results and performance guarantees for data-driven Model Predictive Control (MPC) for constrained linear systems. In its simplest form, imitation learning is an approach that tries to learn an expert policy by querying samples from an expert. Recent approaches to data-driven MPC have used the simplest form of imitation learning known as behavior cloning to learn controllers that mimic the performance of MPC by online sampling of the trajectories of the closed-loop MPC system. Behavior cloning, however, is a method that is known to be data inefficient and suffer from distribution shifts. As an alternative, we develop a variant of the forward training algorithm which is an on-policy imitation learning method proposed by Ross et al. (2010). Our algorithm uses the structure of constrained linear MPC, and our analysis uses the properties of the explicit MPC solution to theoretically bound the number of online MPC trajectories needed to achieve optimal performance. We validate our results through simulations and show that the forward training algorithm is indeed superior to behavior cloning when applied to MPC.