Source author record

Andrea Martinelli

Andrea Martinelli appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.OC eess.SY Systems and Control Computational Complexity Machine Learning

Catalog footprint

What is connected

4works

5topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2026arXiv

Complexity Thresholds for the Constrained Colored Token Swapping Problem

Consider the following puzzle: a farmland consists of several fields, each occupied by either a farmer, a fox, a chicken, or a caterpillar. Creatures in neighboring fields can swap positions as long as the fox avoids the farmer, the chicken avoids the fox, and the caterpillar avoids the chicken. The objective is to decide whether there exists a sequence of swaps that rearranges the creatures into a desired final configuration, while avoiding any unwanted encounters. The above puzzle can be cast an instance of the \emph{colored token swapping} problem with $k = 4$ colors (i.e., creature types), in which only certain pairs of colors can be swapped. We prove that such problem is $\mathsf{PSPACE}$-hard even when the graph representing the farmland is planar and cubic. We also show that the problem is polynomial-time solvable when at most three creature types are involved. We do so by providing a more general algorithm deciding instances with arbitrary values of $k$, as long as the set of all admissible swaps between creature types induces a \emph{spanning star}. Our results settle a problem explicitly left open in [Yang and Zhang, IPL 2025], which established $\mathsf{PSPACE}$-completeness for eight creature types and left the complexity status unresolved when the number of creature types is between three and seven.

preprint2022arXiv

Data-Driven Optimal Control of Affine Systems: A Linear Programming Perspective

In this letter, we discuss the problem of optimal control for affine systems in the context of data-driven linear programming. First, we introduce a unified framework for the fixed point characterization of the value function, Q-function and relaxed Bellman operators. Then, in a model-free setting, we show how to synthesize and estimate Bellman inequalities from a small but sufficiently rich dataset. To guarantee exploration richness, we complete the extension of Willem's fundamental lemma to affine systems.

preprint2022arXiv

PAGE-PG: A Simple and Loopless Variance-Reduced Policy Gradient Method with Probabilistic Gradient Estimation

Despite their success, policy gradient methods suffer from high variance of the gradient estimate, which can result in unsatisfactory sample complexity. Recently, numerous variance-reduced extensions of policy gradient methods with provably better sample complexity and competitive numerical performance have been proposed. After a compact survey on some of the main variance-reduced REINFORCE-type methods, we propose ProbAbilistic Gradient Estimation for Policy Gradient (PAGE-PG), a novel loopless variance-reduced policy gradient method based on a probabilistic switch between two types of updates. Our method is inspired by the PAGE estimator for supervised learning and leverages importance sampling to obtain an unbiased gradient estimator. We show that PAGE-PG enjoys a $\mathcal{O}\left( ε^{-3} \right)$ average sample complexity to reach an $ε$-stationary solution, which matches the sample complexity of its most competitive counterparts under the same setting. A numerical evaluation confirms the competitive performance of our method on classical control tasks.

preprint2020arXiv

Control of Networked Systems by Clustering: The Degree of Freedom Concept

We address the problem of local flux redistribution in networked systems. The aim is to detect a suitable cluster which is able to locally adsorb a disturbance by means of an appropriate redistribution of control load among its nodes, such that no external node is affected. Traditional clustering measures are not suitable for our purpose, since they do not explicitly take into account the structural conditions for disturbance containment. We propose a new measure based on the concept of degree of freedom for a cluster, and we introduce a heuristic procedure to quickly select a set of nodes according to this measure. Finally, we show an application of the method in the context of DC microgrids voltage control.