paginate_links 'base' and 'format'

Question

I am using paginate_links() to display the pagination from an ajax call.

This is my code

<?php 
    $big = 999999999; // need an unlikely integer       
    $pagination = paginate_links(array(
        'mid_size'  => 2,
        'prev_text' =>esc_html__('Previous', 'travel-tour'),
        'next_text' => esc_html__('Next', 'travel-tour'),
        'current' => max( 1, get_query_var('paged') ),
        'total' => $cat_query->max_num_pages,
        'type' => 'array',
        'base'      => '%_%',
        'format'    => '/paged/%#%',

    ) );
    echo '<li>' . implode( '</li><li>', $pagination ) . '</li>';
?>

When I try to change the 'format' => '?paged/%#%' with the ? character then it works, the url is shown like this (//localhost/mysite.com/video/packages/?paged/2)

but when I change it to 'format' => '/paged/%#%' with the / character then it shows like this //localhost/paged/2

I need it to look like this without the ? character //localhost/mysite.com/video/packages/paged/2

Hope this makes sense, thanks

This is the complete code that I have

<?php
add_action( 'wp_ajax_nopriv_load-filter', 'prefix_load_cat_posts' );
add_action( 'wp_ajax_load-filter', 'prefix_load_cat_posts' );

function prefix_load_cat_posts () {
    global $post,  $wp_query, $wp_rewrite;

    $cat_id = $_POST[ 'cat' ];

    $paged = ( get_query_var( 'paged' ) ) ? absint( get_query_var( 'paged' ) ) : 1;

    $args = array (
        'cat' => $cat_id,
        'posts_per_page' => 6,
        'order' => 'DESC',
        'paged' => $paged
    );

    $cat_query = new WP_Query($args);

    if($cat_query->have_posts()) :
        while($cat_query->have_posts()) : $cat_query->the_post();
            get_template_part( 'template-parts/content', get_post_format() );
        endwhile;
        wp_reset_query();
?>
    <div class="page-nation">
        <ul class="pagination pagination-large">
        <?php 
            $big = 999999999; // need an unlikely integer       
            $pagination = paginate_links(array(
                'mid_size'  => 2,
                'prev_text' =>esc_html__('Previous', 'travel-tour'),
                'next_text' => esc_html__('Next', 'travel-tour'),
                'current' => max( 1, get_query_var('paged') ),
                'total' => $cat_query->max_num_pages,
                'type' => 'array',
                'base'      => '%_%',
                'format'    => '?paged/%#%',

            ) );
            echo '<li>' . implode( '</li><li>', $pagination ) . '</li>';
        ?>
        </ul>
    </div> 
<?php
    endif;

}